The complexity of degree anonymization by vertex addition

DOI10.1016/j.tcs.2015.07.004zbMath1332.68164OpenAlexW766556958WikidataQ62039078 ScholiaQ62039078MaRDI QIDQ897957

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

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

NP-hardnessfixed-parameter tractabilityparameterized 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)

Related Items

The complexity of degree anonymization by graph contractions ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Finding large degree-anonymous subgraphs is hard ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Solving MAX-\(r\)-SAT above a tight lower bound
• Advice classes of parametrized tractability
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• A refined complexity analysis of degree anonymization in graphs
• Parametrized complexity theory.
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• Parameterized Inapproximability of Degree Anonymization
• The Complexity of Degree Anonymization by Graph Contractions
• Integer Programming with a Fixed Number of Variables
• Reflections on Multivariate Algorithmics and Problem Parameterization
• A remark on the existence of finite graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• The Complexity of Degree Anonymization by Vertex Addition