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 16,320
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
(1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-57811-0 · Cited by 417
On the Foundations of Combinatorial Theory
Rota, G. (2009) · Birkhäuser Boston eBooks · doi:10.1007/978-0-8176-4842-8_25 · Cited by 390
A new algorithm for optimal 2-constraint satisfaction and its implications
Williams, R. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.09.023 · Cited by 386
A Bayesian Approach to Learning Bayesian Networks with Local Structure
Chickering, D. M., Heckerman, D. E., & Meek, C. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.1528 · Cited by 314
The Complexity of Counting in Sparse, Regular, and Planar Graphs
Vadhan, S. P. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539797321602 · Cited by 250
Fürer, M. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250800 · Cited by 240
A still better performance guarantee for approximate graph coloring
Halldórsson, M. M. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90246-6 · Cited by 224
Bayesian Clustering and Product Partition Models
Quintana, F. A., & Iglesias, P. L. (2003) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/1467-9868.00402 · Cited by 194
Beigel, R., & Eppstein, D. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.06.008 · Cited by 163
Measure and conquer: a simple O(20.288n) independent set algorithm
Fomin, F. V., Grandoni, F., & Kratsch, D. (2006) · doi:10.5555/1109557.1109560 · Cited by 114
Space and Time Complexity of Exact Algorithms: Some Open Problems
Woeginger, G. J. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28639-4_25 · Cited by 83
Worst-case time bounds for coloring and satisfiability problems
Feder, T., & Motwani, R. (2002) · Journal of Algorithms · doi:10.1016/s0196-6774(02)00224-9 · Cited by 36
Algorithms to count paths and cycles
Bax, E. T. (1994) · Information Processing Letters · doi:10.1016/0020-0190(94)00151-0 · Cited by 33
A finite-difference sieve to count paths and cycles by length
Bax, E. T., & Franklin, J. (1996) · Information Processing Letters · doi:10.1016/s0020-0190(96)00159-7 · Cited by 31
Algorithms for Counting 2-Sat Solutions and Colorings with Applications
Fürer, M., & Kasiviswanathan, S. P. (2007) · Springer eBooks · doi:10.1007/978-3-540-72870-2_5 · Cited by 28
Optimal 2-constraint satisfaction via sum–product algorithms
Koivisto, M. (2006) · Information Processing Letters · doi:10.1016/j.ipl.2005.11.013 · Cited by 19
Self-citationAn improved exact algorithm for the domatic number problem
Riege, T., Rothe, J., Spakowski, H., & Yamamoto, M. (2006) · Information Processing Letters · doi:10.1016/j.ipl.2006.08.010 · Cited by 17
Partitioning Based Algorithms for Some Colouring Problems
Angelsmark, O., & Thapper, J. (2006) · Lecture notes in computer science · doi:10.1007/11754602_4 · Cited by 12
Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
Björklund, A., & Husfeldt, T. (2006) · Lecture notes in computer science · doi:10.1007/11786986_48 · Cited by 9
Self-citation
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
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.