Du är här

Inclusion-exclusion algorithms for counting set partitions

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 Computer Society

Sammanfattning

Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) 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 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and (1 + ϵ)χ(G) in time O(1.2209n + 2.2461e-ϵn)

Disputation

Nyckelord

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

Övriga

2006 47th Annual IEEE Conference on Foundations of Computer Science
21-24 Oct. 2006
Berkeley, CA, USA
Published
Yes
  • ISBN: 0-7695-2720-5

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

LERU logotype U21 logotype

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen