Graph editing to a given degree sequence

DOI10.1016/j.tcs.2016.12.007zbMath1356.68098arXiv1601.03174OpenAlexW4210637083MaRDI QIDQ507592

Petr A. Golovach, George B. Mertzios

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.03174

zbMATH Keywords

degree sequenceparameterized complexitygraph editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex degrees (05C07)

Related Items (3)

A survey of parameterized algorithms and the complexity of edge modification ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Dividing splittable goods evenly and with limited fragmentation

Cites Work

• Unnamed Item
• 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