The Complexity of Finding a Large Subgraph under Anonymity Constraints

DOI10.1007/978-3-642-45030-3_15zbMATH Open1329.05276OpenAlexW20210139MaRDI QIDQ2872080FDOQ2872080

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

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

Mathematics Subject Classification ID

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

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)