The DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Set Partitioning via Inclusion-Exclusion
Abstract
Given a set N with n elements and a family $\mathcal{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 $\mathcal{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 $\lceil(1+\epsilon)\chi(G)\rceil$ in time $O(1.2209^n+2.2461^{e^{-\epsilon}n})$.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 15,999
Jain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199
Biggs, N. (1974) · doi:10.1017/cbo9780511608704 · Cited by 2,940
Model-Based Gaussian and Non-Gaussian Clustering
Banfield, J. D., & Raftery, A. E. (1993) · Biometrics · doi:10.2307/2532201 · Cited by 2,395
Unsupervised learning of finite mixture models
Figueiredo, M. A. T., & Jain, A. K. (2002) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.990138 · Cited by 2,125
On the foundations of combinatorial theory I. Theory of M�bius Functions
Rota, G. C. (1964) · Zeitschrift f�r Wahrscheinlichkeitstheorie und Verwandte Gebiete · doi:10.1007/bf00531932 · Cited by 1,476
Schnelle Multiplikation großer Zahlen
Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107
Exact Algorithms for NP-Hard Problems: A Survey
Woeginger, G. J. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36478-1_17 · Cited by 652
Design and Analysis of Factorial Experiments
Yates, F. (1958) · Rothamsted Repository (Rothamsted Repository) · Cited by 467
Cited by
Fomin, F. V., & Kratsch, D. (2010) · Texts in Theoretical Computer Science. An EATCS Series · doi:10.1007/978-3-642-16533-7 · Cited by 471
Metadata
- Authors
- Björklund, A., Husfeldt, T., & Koivisto, M.
- Venue
- SIAM Journal on Computing
- Published
- 2009-01
- Volume
- 39
- Issue
- 2
- Pages
- 546-563
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2074359677
- Cited by
- 370
- References
- 29
- FWCI
- 26.72
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Set Partitioning via Inclusion-Exclusion. https://app.cochat.ai/papers/10.1137/070683933
- The paper
- Björklund, A., Husfeldt, T., & Koivisto, M. (2009). Set Partitioning via Inclusion-Exclusion. SIAM Journal on Computing. https://doi.org/10.1137/070683933
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.