Parameterized Complexity of k-Anonymity: Hardness and Tractability

DOI10.1007/978-3-642-19222-7_25zbMath1326.68155OpenAlexW4254264926MaRDI QIDQ3000512

Riccardo Dondi, Gianluca Della Vedova, Yuri Pirola, Paola Bonizzoni

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

The \(l\)-diversity problem: tractability and approximability ⋮ The effect of homogeneity on the computational complexity of combinatorial data anonymization ⋮ The Effect of Homogeneity on the Complexity of k-Anonymity

Cites Work

• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Achieving anonymity via clustering
• On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
• The k-Anonymity Problem Is Hard
• k-Anonymization with Minimal Loss of Information
• Resolving the Complexity of Some Data Privacy Problems
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Database Theory - ICDT 2005
• Experimental and Efficient Algorithms

This page was built for publication: Parameterized Complexity of k-Anonymity: Hardness and Tractability