The price of connectivity for feedback vertex set
The price of connectivity for feedback vertex set
复制标题
反馈顶点集的连接价格
DOI：
10.1016/j.dam.2016.08.011
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
Belmonte R
中科院分区：
文献类型：
--
作者：
Belmonte R
设fvs（G）和cfvs（G）分别表示图G的最小反馈点集和最小连通反馈点集的基数.一类图G的反馈点集连通度的代价定义为所有连通图G∈ G上的最大比率cfvs（G）/fvs（G）.本文研究了由有限个禁止导出子图族H定义的图类的POC-FVS。我们精确地刻画了H-无图的poc-fvs上界为常数的有限族H。此外，对于H = 1的情形，我们精确地确定了那些存在常数c H使得对每个连通的无H图G，cfvs（G）≤ fvs（G）+ c H的图H，以及那些我们可以取c H= 0的图H。
Let fvs (G) and cfvs (G) denote the cardinalities of a minimum feedback vertex set and a minimum connected feedback vertex set of a graph G, respectively. The price of connectivity for feedback vertex set (poc-fvs) for a class of graphs G is defined as the maximum ratio cfvs (G)/fvs (G) over all connected graphs G∈ G. We study the poc-fvs for graph classes defined by a finite family H of forbidden induced subgraphs. We characterize exactly those finite families H for which the poc-fvs for H-free graphs is upper bounded by a constant. Additionally, for the case where∣ H∣= 1, we determine exactly those graphs H for which there exists a constant c H such that cfvs (G)≤ fvs (G)+ c H for every connected H-free graph G, as well as exactly those graphs H for which we can take c H= 0.
登录
查看更多内容
DOI：
10.7151/dmgt.1192
发表时间：
2003
期刊：
Discuss. Math. Graph Theory
影响因子：
--
作者：
I. Zverovich
通讯作者：
I. Zverovich
影响因子：
1.1
作者：
Eglantine Camby;Oliver Schaudt
通讯作者：
Oliver Schaudt
关于无长路径和循环图中连通支配集的注记
DOI：
--
发表时间：
2013
期刊：
arXiv.org
影响因子：
--
作者：
Eglantine Camby;Oliver Schaudt
通讯作者：
Oliver Schaudt
平面图中的连通反馈顶点集
DOI：
--
发表时间：
2009
期刊：
International Workshop on Graph-Theoretic Concepts in Computer Science
影响因子：
--
作者：
A. Grigoriev;René Sitters
通讯作者：
René Sitters
Vertex Cover 连接的价格
影响因子：
0.7
作者：
Eglantine Camby;J. Cardinal;Samuel Fiorini;Oliver Schaudt
通讯作者：
Oliver Schaudt