A refined complexity analysis of degree anonymization in graphs

DOI10.1016/J.IC.2014.12.017zbMATH Open1327.68134OpenAlexW2051603732MaRDI QIDQ2347809FDOQ2347809

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

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

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)

Cites Work

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

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
• Finding large degree-anonymous subgraphs is hard
• A survey of parameterized algorithms and the complexity of edge modification
• Degree-anonymization using edge rotations
• 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)