Finding large degree-anonymous subgraphs is hard
From MaRDI portal
Publication:5964077
DOI10.1016/j.tcs.2016.02.004zbMath1335.68095OpenAlexW2260327309MaRDI QIDQ5964077
André Nichterlein, Sepp Hartung, Robert Bredereck, Gerhard J. Woeginger, Cristina Bazgan
Publication date: 26 February 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.004
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (5)
Win-win kernelization for degree sequence completion problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Degree-anonymization using edge rotations ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The complexity of degree anonymization by vertex addition
- Parameterized complexity of finding regular induced subgraphs
- A refined complexity analysis of degree anonymization in graphs
- Editing to a graph of given degrees
- Parametrized complexity theory.
- The Complexity of Finding a Large Subgraph under Anonymity Constraints
- Parameterized Inapproximability of Degree Anonymization
- The Complexity of Degree Anonymization by Graph Contractions
- Emergence of Scaling in Random Networks
- Deciding first-order properties of locally tree-decomposable structures
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Graph Classes: A Survey
- Kernelization Lower Bounds Through Colors and IDs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Finding large degree-anonymous subgraphs is hard
