Parameterized inapproximability of degree anonymization

DOI10.1007/978-3-319-13524-3_7zbMATH Open1456.68062OpenAlexW165003445MaRDI QIDQ2946009FDOQ2946009

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

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

Mathematics Subject Classification ID

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

Cited In (9)

• Approximating degree sequences with regular graphic sequences (extended abstract)
• A refined complexity analysis of degree anonymization in graphs
• The complexity of degree anonymization by graph contractions
• Finding large degree-anonymous subgraphs is hard
• Degree-anonymization using edge rotations
• The complexity of degree anonymization by vertex addition
• Degree-constrained editing of small-degree graphs
• Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
• A refined complexity analysis of degree anonymization in graphs

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)