Meny

Javascript is not activated in your browser. This website needs javascript activated to work properly.
Du är här

Set partitioning via inclusion-exclusion

Författare:
Publiceringsår: 2009
Språk: Engelska
Sidor: 546-563
Publikation/Tidskrift/Serie: SIAM Journal on Computing
Volym: 39
Nummer: 2
Dokumenttyp: Artikel
Förlag: SIAM Publications

Sammanfattning

Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)).

Disputation

Nyckelord

  • Technology and Engineering
  • exact algorithm
  • set partition
  • inclusion-exclusion
  • graph coloring
  • zeta transform

Övriga

  • VR
Published
  • Exact algorithms
Yes
  • Algorithms
  • ISSN: 0097-5397

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

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