Editing graphs to satisfy degree constraints: A parameterized approach

Publication Type:
Journal Article
Citation:
Journal of Computer and System Sciences, 2012, 78 (1), pp. 179 - 191
Issue Date:
2012-01-01
Full metadata record
Files in This Item:
Filename Description Size
1-s2.0-S0022000011000067-main.pdfPublished Version253.65 kB
Adobe PDF
We study a wide class of graph editing problems that ask whether a given graph can be modified to satisfy certain degree constraints, using a limited number of vertex deletions, edge deletions, or edge additions. The problems generalize several well-studied problems such as the General Factor Problem and the Regular Subgraph Problem. We classify the parameterized complexity of the considered problems taking upper bounds on the number of editing steps and the maximum degree of the resulting graph as parameters. © 2011 Elsevier Inc. All rights reserved.
Please use this identifier to cite or link to this item: