Editing graphs to satisfy degree constraints: A parameterized approach
Editing graphs to satisfy degree constraints: A parameterized approach
复制标题
DOI：
10.1016/j.jcss.2011.02.001
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Luke Mathieson;Stefan Szeider
中科院分区：
文献类型：
--
作者：
Luke Mathieson;Stefan Szeider
我们研究了一类广泛的图形编辑问题，询问是否可以修改给定的图，以满足一定程度的约束，使用有限数量的顶点删除，删除边，或添加边。这些问题推广了已有的几个问题，如一般因子问题和正则子图问题。我们分类的参数化的复杂性所考虑的问题上界的编辑步骤的数量和所得到的图形的最大程度作为参数。
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.