On the Complexity of the Minimum Independent Set Partition Problem

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

zbMATH Keywords

data privacyMISPDualvoting verification

Mathematics Subject Classification ID

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

This page was built for publication: On the Complexity of the Minimum Independent Set Partition Problem