A refined complexity analysis of degree anonymization in graphs

DOI10.1016/J.IC.2014.12.017MaRDI QIDQ2347809zbMATH OpenOpenAlexFDO

Authors Sepp Hartung, André Nichterlein, Ondřej Suchý, 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

\(f\)-factorsdata privacyheuristicskernelizationparameterized complexity

Mathematics Subject Classification ID

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

Recommendations

• A refined complexity analysis of degree anonymization in graphs
• The complexity of degree anonymization by graph contractions
• The complexity of degree anonymization by graph contractions
• The complexity of degree anonymization by vertex addition
• The complexity of degree anonymization by vertex addition
• Parameterized inapproximability of degree anonymization
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• De-anonymization of heterogeneous random graphs in quasilinear time
• De-anonymization of heterogeneous random graphs in quasilinear time

Cites work

• Achieving anonymity via clustering
• Anonymizing binary and small tables is hard to approximate
• Editing graphs to satisfy degree constraints: a parameterized approach
• Fixed-parameter tractability of anonymizing data by suppressing entries
• Fundamentals of parameterized complexity
• Graph theory
• Heuristic algorithms in computational molecular biology
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1467781 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• Kernelization: new upper and lower bound techniques
• Matching theory
• New races in parameterized algorithmics
• On the parameterized complexity of multiple-interval graph problems
• Parameterized complexity of \(k\)-anonymity: hardness and tractability
• Parameterized complexity of finding regular induced subgraphs
• Parameterized inapproximability of degree anonymization
• Parametrized complexity theory.
• Recent developments in kernelization: a survey
• Reflections on multivariate algorithmics and problem parameterization
• The asymmetric median tree. --- A new model for building consensus trees
• The complexity of degree anonymization by vertex addition
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity

Cited in

(24)

• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• De-anonymization of heterogeneous random graphs in quasilinear time
• Degree-anonymization using edge rotations
• \((k, l)\)-anonymity in wheel-related social graphs measured on the base of \(k\)-metric antidimension
• Graphic sequences, distances and \(k\)-degree anonymity
• The complexity of degree anonymization by graph contractions
• On the complexity of \(k\)-metric antidimension problem and the size of \(k\)-antiresolving sets in random graphs
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Approximating degree sequences with regular graphic sequences (extended abstract)
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• Parameterized inapproximability of degree anonymization
• The complexity of degree anonymization by graph contractions
• Win-win kernelization for degree sequence completion problems
• Graph editing to a given degree sequence
• The complexity of degree anonymization by vertex addition
• Differential privacy in probabilistic systems
• A refined complexity analysis of degree anonymization in graphs
• Graph editing to a given degree sequence
• Finding large degree-anonymous subgraphs is hard
• A survey of parameterized algorithms and the complexity of edge modification
• Degree-constrained editing of small-degree graphs
• Obtaining k-degree anonymous networks via mathematical programming
• The complexity of degree anonymization by vertex addition
• KDVEM: a \(k\)-degree anonymity with vertex and edge modification algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347809)