On the Complexity of the Minimum Independent Set Partition Problem

DOI10.1007/978-3-319-21398-9_10zbMATH Open1468.05016OpenAlexW1160767717MaRDI QIDQ3196378FDOQ3196378

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A threshold of ln n for approximating set cover
• Reducibility among Combinatorial Problems
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Probabilistic checking of proofs
• Some optimal inapproximability results
• The complexity of theorem-proving procedures
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Zero knowledge and the chromatic number
• The vector partition problem for convex objective functions.

Cited In (5)

• Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms
• 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)