The complexity of degree anonymization by vertex addition

DOI10.1016/J.TCS.2015.07.004MaRDI QIDQ897957zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A refined complexity analysis of degree anonymization in graphs
• A remark on the existence of finite graphs
• Advice classes of parametrized tractability
• Fundamentals of parameterized complexity
• Integer Programming with a Fixed Number of Variables
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Parameterized inapproximability of degree anonymization
• Parametrized complexity theory.
• Recent developments in kernelization: a survey
• Reflections on multivariate algorithmics and problem parameterization
• Solving MAX-\(r\)-SAT above a tight lower bound
• 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
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity

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)