The Complexity of Finding a Large Subgraph under Anonymity Constraints

DOI10.1007/978-3-642-45030-3_15MaRDI QIDQ2872080zbMATH OpenOpenAlexFDO

Authors Robert Bredereck, Sepp Hartung, André Nichterlein, Gerhard J. Woeginger

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_15

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Symbolic computation and algebraic computation (68W30)

Recommendations

• Finding large degree-anonymous subgraphs is hard
• The anonymous subgraph problem
• 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
• The complexity of degree anonymization by vertex addition
• The complexity of degree anonymization by vertex addition

Cited in

(10)

• The complexity of degree anonymization by graph contractions
• De-anonymization of heterogeneous random graphs in quasilinear time
• De-anonymization of heterogeneous random graphs in quasilinear time
• Finding large degree-anonymous subgraphs is hard
• The complexity of degree anonymization by vertex addition
• The anonymous subgraph problem
• Graph editing to a given degree sequence
• On the computational complexities of three problems related to a privacy measure for large networks under active attack
• Graph editing to a given degree sequence
• A refined complexity analysis of degree anonymization in graphs

This page was built for publication: The Complexity of Finding a Large Subgraph under Anonymity Constraints

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