A refined complexity analysis of degree anonymization in graphs

DOI10.1016/j.ic.2014.12.017zbMath1327.68134OpenAlexW2051603732MaRDI QIDQ2347809

Ondřej Suchý, André Nichterlein, Sepp Hartung, Rolf Niedermeier

Publication date: 9 June 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.12.017

zbMATH Keywords

heuristicsparameterized complexitydata privacykernelization\(f\)-factors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Win-win kernelization for degree sequence completion problems ⋮ The complexity of degree anonymization by graph contractions ⋮ The complexity of degree anonymization by vertex addition ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Graph editing to a given degree sequence ⋮ Differential privacy in probabilistic systems ⋮ Graph Editing to a Given Degree Sequence ⋮ Degree-anonymization using edge rotations ⋮ Finding large degree-anonymous subgraphs is hard ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Anonymizing binary and small tables is hard to approximate
• Heuristic algorithms in computational molecular biology
• Fixed-parameter tractability of anonymizing data by suppressing entries
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of finding regular induced subgraphs
• Matching theory
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Parametrized complexity theory.
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• New Races in Parameterized Algorithmics
• Achieving anonymity via clustering
• Parameterized Inapproximability of Degree Anonymization
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Kernelization: New Upper and Lower Bound Techniques
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• The Complexity of Degree Anonymization by Vertex Addition
• The asymmetric median tree. --- A new model for building consensus trees

This page was built for publication: A refined complexity analysis of degree anonymization in graphs