Parameterized complexity of k-anonymity: hardness and tractability
DOI10.1007/S10878-011-9428-9zbMATH Open1300.90033OpenAlexW3098107898MaRDI QIDQ358665FDOQ358665
Authors: Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola 
Publication date: 9 August 2013
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-011-9428-9
Recommendations
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Fixed-parameter tractability of anonymizing data by suppressing entries
- Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries
- The k-Anonymity Problem Is Hard
- Anonymizing binary and small tables is hard to approximate
Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Some APX-completeness results for cubic graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- Title not available (Why is that?)
- k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Achieving anonymity via clustering
- On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
- Resolving the Complexity of Some Data Privacy Problems
- Database Theory - ICDT 2005
- Anonymizing binary and small tables is hard to approximate
- Fixed-parameter tractability of anonymizing data by suppressing entries
Cited In (18)
- The \(l\)-diversity problem: tractability and approximability
- Hardness of \(k\)-anonymous microaggregation
- The effect of homogeneity on the computational complexity of combinatorial data anonymization
- Error detection and correction of gene trees
- Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries
- Privacy in elections: \(k\)-anonymizing preference orders
- Pattern-guided \(k\)-anonymity
- The k-Anonymity Problem Is Hard
- On the complexity of the \(l\)-diversity problem
- The effect of homogeneity on the complexity of \(k\)-anonymity
- A fixed-parameter approach for privacy-protection with global recoding
- \(k\)-attribute-anonymity is hard even for \(k=2\)
- Database Theory - ICDT 2005
- A refined complexity analysis of degree anonymization in graphs
- Anonymizing binary and small tables is hard to approximate
- Fixed-parameter tractability of anonymizing data by suppressing entries
- Pattern-guided \(k\)-anonymity
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
Uses Software
This page was built for publication: Parameterized complexity of \(k\)-anonymity: hardness and tractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q358665)
