The complexity of degree anonymization by vertex addition

DOI10.1016/J.TCS.2015.07.004zbMATH Open1332.68164OpenAlexW766556958WikidataQ62039078 ScholiaQ62039078MaRDI QIDQ897957FDOQ897957

Authors: Robert Bredereck, Vincent Froese, Sepp Hartung, André Nichterlein, Rolf Niedermeier, Nimrod Talmon 

Publication date: 8 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.004

Recommendations

• The complexity of degree anonymization by vertex addition
• A refined complexity analysis of degree anonymization in graphs
• 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

zbMATH Keywords

fixed-parameter tractabilityNP-hardnessparameterized complexitykernelizationgraph modificationdegree-constrained editing

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) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• Recent developments in kernelization: a survey
• Title not available (Why is that?)
• Solving MAX-\(r\)-SAT above a tight lower bound
• Title not available (Why is that?)
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• A remark on the existence of finite graphs
• A refined complexity analysis of degree anonymization in graphs
• Advice classes of parametrized tractability
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Reflections on multivariate algorithmics and problem parameterization
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• The complexity of degree anonymization by graph contractions
• The complexity of degree anonymization by vertex addition
• Parameterized inapproximability of degree anonymization

Cited In (12)

• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• 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
• \(k\)-anonymous path privacy on social graphs
• 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
• KDVEM: a \(k\)-degree anonymity with vertex and edge modification algorithm
• Parameterized inapproximability of degree anonymization
• A refined complexity analysis of degree anonymization in graphs
• The complexity of degree anonymization by vertex addition

This page was built for publication: The complexity of degree anonymization by vertex addition

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