The complexity of degree anonymization by graph contractions

DOI10.1016/j.ic.2017.07.007zbMath1376.68069OpenAlexW2736279681WikidataQ62039061 ScholiaQ62039061MaRDI QIDQ2407102

Nimrod Talmon, Sepp Hartung

Publication date: 28 September 2017

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2017.07.007

zbMATH Keywords

computational complexityprivacyfixed-parameter tractabilityparameterized complexitygraph modificationsdegree-constrained editingdata publishing

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)

Related Items

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized complexity of three edge contraction problems with degree constraints
• Edge-contraction problems
• The complexity of degree anonymization by vertex addition
• Multigraph realizations of degree sequences: Maximization is easy, minimization is hard
• Obtaining planarity by contracting few edges
• A refined complexity analysis of degree anonymization in graphs
• Partition into triangles on bounded degree graphs
• Contracting graphs to paths and trees
• A faster FPT algorithm for bipartite contraction
• 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
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Algorithms – ESA 2004