Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

Inclusion-exclusion algorithms for counting set partitions

Författare

Summary, in English

Given a set U with n elements and a family of subsets S ⊆ 2<sup>U</sup> we show how to count the number of k-partitions S<sub>1</sub> ∪ ... ∪ S<sub>k</sub> = U into subsets S<sub>i</sub> ∈ S in time 2<sup>n</sup>n<sup>O(1)</sup>. The only assumption on S is that it can be enumerated in time 2<sup>n</sup>n<sup>O(1)</sup>. In effect we get exact algorithms in time 2<sup>n</sup>n<sup>O(1)</sup> for several well-studied partition problems including domatic number, chromatic number, bounded component spanning forest, partition into Hamiltonian subgraphs, and bin packing. If only polynomial space is available, our algorithms run in time 3<sup>n</sup>n<sup>O(1)</sup> if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461<sup>n</sup>) and polynomial space. For domatic number, we present a version that runs in time O(2.8718<sup>n</sup>). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209<sup>n</sup> + 2.2461<sup>e-ϵ</sup>n)

Publiceringsår

2006

Språk

Engelska

Sidor

575-582

Publikation/Tidskrift/Serie

2006 47th Annual IEEE Conference on Foundations of Computer Science

Dokumenttyp

Konferensbidrag

Förlag

IEEE - Institute of Electrical and Electronics Engineers Inc.

Ämne

  • Computer Science

Nyckelord

  • polynomial space approximation
  • bin packing
  • Hamiltonian subgraph
  • bounded component spanning forest
  • chromatic number
  • domatic number
  • inclusion-exclusion algorithm
  • counting set partition

Conference name

2006 47th Annual IEEE Conference on Foundations of Computer Science

Conference date

2006-10-21 - 2006-10-24

Conference place

Berkeley, CA, United States

Status

Published

ISBN/ISSN/Övrigt

  • ISBN: 0-7695-2720-5