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

heuristicsdata privacyparameterized complexitykernelization\(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)

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

• 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?)
• 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
• 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 Complexity of Finding a Large Subgraph under Anonymity Constraints
• The asymmetric median tree. --- A new model for building consensus trees
• The complexity of degree anonymization by vertex addition
• The effect of homogeneity on the computational complexity of combinatorial data anonymization
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

Cited in

(23)

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

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)