Parameterized complexity of k-anonymity: hardness and tractability

DOI10.1007/978-3-642-19222-7_25MaRDI QIDQ3000512zbMATH OpenOpenAlexFDO

Authors Gianluca Della Vedova, Riccardo Dondi, 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

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

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
• The effect of homogeneity on the complexity of \(k\)-anonymity

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Achieving anonymity via clustering
• Database Theory - ICDT 2005
• Experimental and Efficient Algorithms
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability of anonymizing data by suppressing entries
• On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
• Resolving the Complexity of Some Data Privacy Problems
• The k-Anonymity Problem Is Hard
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• k-Anonymization with Minimal Loss of Information

Cited in

(13)

• The \(l\)-diversity problem: tractability and approximability
• Privacy in elections: \(k\)-anonymizing preference orders
• On the complexity of the \(l\)-diversity problem
• The effect of homogeneity on the complexity of \(k\)-anonymity
• Hardness of \(k\)-anonymous microaggregation
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• A fixed-parameter approach for privacy-protection with global recoding
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Anonymizing binary and small tables is hard to approximate
• Fixed-parameter tractability of anonymizing data by suppressing entries
• The k-Anonymity Problem Is Hard
• \(k\)-attribute-anonymity is hard even for \(k=2\)
• Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries

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 Q3000512)