On the complexity of the minimum independent set partition problem

DOI10.1007/978-3-319-21398-9_10MaRDI QIDQ3196378zbMATH OpenOpenAlexFDO

Authors 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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Partitions of sets (05A18) Voting theory (91B12)

Recommendations

• On the complexity of approximating the independent set problem
• On approximating the minimum independent dominating set
• Privacy in elections: \(k\)-anonymizing preference orders
• scientific article; zbMATH DE number 2044526
• Private approximation of NP-hard functions

Cites work

• scientific article; zbMATH DE number 3495588 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Probabilistic checking of proofs
• Reducibility among combinatorial problems
• Some optimal inapproximability results
• The complexity of theorem-proving procedures
• The vector partition problem for convex objective functions.
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Zero knowledge and the chromatic number
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

Cited in

(4)

• The minimum weakly connected independent set problem: polyhedral results and branch-and-cut
• On the Minimum Common Integer Partition Problem
• On the minimum consistent subset problem
• Better Approximations for the Minimum Common Integer Partition Problem

This page was built for publication: On the complexity of the minimum independent set partition problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196378)