Graph Editing to a Given Degree Sequence

DOI10.1007/978-3-319-34171-2_13zbMath1475.68139OpenAlexW2235753326MaRDI QIDQ5740185

George B. Mertzios, Petr A. Golovach

Publication date: 25 July 2016

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/17999/1/17999.pdf

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Editing graphs to satisfy degree constraints: a parameterized approach
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of finding regular induced subgraphs
• General factors of graphs
• A refined complexity analysis of degree anonymization in graphs
• Editing to a graph of given degrees
• Parameterized complexity of Eulerian deletion problems
• The Complexity of Finding a Large Subgraph under Anonymity Constraints
• Editing to a Connected Graph of Given Degrees
• The Complexity of Degree Anonymization by Graph Contractions
• Emergence of Scaling in Random Networks
• Win-Win Kernelization for Degree Sequence Completion Problems
• Editing to a Planar Graph of Given Degrees
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The spanning subgraphs of eulerian graphs
• Color-coding
• Kernelization Lower Bounds by Cross-Composition
• The Complexity of Degree Anonymization by Vertex Addition
• Parameterized Algorithms

This page was built for publication: Graph Editing to a Given Degree Sequence