Parameterized inapproximability of degree anonymization

DOI10.1007/978-3-319-13524-3_7MaRDI QIDQ2946009zbMATH OpenOpenAlexFDO

Authors André Nichterlein, Cristina Bazgan

Publication date 15 September 2015

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13524-3_7

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Finding large degree-anonymous subgraphs is hard
• A refined complexity analysis of degree anonymization in graphs
• 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

Cited in

(9)

• Degree-anonymization using edge rotations
• Approximating degree sequences with regular graphic sequences (extended abstract)
• A refined complexity analysis of degree anonymization in graphs
• A refined complexity analysis of degree anonymization in graphs
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• 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 graph contractions

This page was built for publication: Parameterized inapproximability of degree anonymization

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