On the Complexity of the Minimum Independent Set Partition Problem
From MaRDI portal
Publication:3196378
DOI10.1007/978-3-319-21398-9_10zbMath1468.05016OpenAlexW1160767717MaRDI QIDQ3196378
T.-H. Hubert Chan, Charalampos Papamanthou, Zhichao Zhao
Publication date: 29 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_10
Partitions of sets (05A18) Voting theory (91B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Zero knowledge and the chromatic number
- The Vector Partition Problem for Convex Objective Functions
- A threshold of ln n for approximating set cover
- Probabilistic checking of proofs
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
- Reducibility among Combinatorial Problems
- Some optimal inapproximability results
- The complexity of theorem-proving procedures