A refined complexity analysis of degree anonymization in graphs

DOI10.1007/978-3-642-39212-2_52MaRDI QIDQ5327468zbMATH OpenOpenAlexFDO

Authors Sepp Hartung, André Nichterlein, Rolf Niedermeier, Ondřej Suchý

Publication date 7 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39212-2_52

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A refined complexity analysis of degree anonymization in graphs
• The complexity of degree anonymization by vertex addition
• The complexity of degree anonymization by vertex addition
• Finding large degree-anonymous subgraphs is hard
• Parameterized inapproximability of degree anonymization

Cited in

(14)

• Degree-anonymization using edge rotations
• Graphic sequences, distances and \(k\)-degree anonymity
• A refined complexity analysis of degree anonymization in graphs
• The complexity of degree anonymization by graph contractions
• On the complexity of \(k\)-metric antidimension problem and the size of \(k\)-antiresolving sets in random graphs
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• Parameterized inapproximability of degree anonymization
• Privacy in elections: k-anonymizing preference orders
• The complexity of degree anonymization by graph contractions
• The complexity of degree anonymization by vertex addition
• Finding large degree-anonymous subgraphs is hard
• Degree-constrained editing of small-degree graphs
• The complexity of degree anonymization by vertex addition
• KDVEM: a \(k\)-degree anonymity with vertex and edge modification algorithm

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 Q5327468)