On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
复制标题
关于图识别问题和使用路径识别顶点的特殊情况
DOI：
10.1007/978-3-642-35926-2_4
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Matjaz
中科院分区：
文献类型：
--
作者：
Foucaud;Florent;Matjaz
本文介绍了图G的识别路径覆盖问题：图G的识别路径覆盖是使每个顶点都属于一条路径的集合，并且对于每对顶点，存在一条恰好包括一条Ofu，V的路径。这个问题涉及到各种各样的识别问题。我们研究了一些图族中的识别路径覆盖问题。特别地，我们得到了路、圈、超立方体和拓扑不可约树的标识路覆盖的最优大小，并给出了所有树的一个上界。给出了一般图的标识路覆盖的最小长度的上下界，并讨论了它们的紧性。特别地，我们证明了任何连通图G至多有一个可识别的大小的路覆盖。我们还研究了相关优化问题的计算复杂性，特别地，我们证明了当要求路的长度为某一固定值时，问题是APX-完全的。
In this paper, we introduce the identifying path cover problem: anidentifying path coverof a graphGis a setof paths such that each vertex belongs to a path of, and for each pairu,vof vertices, there is a path ofwhich includes exactly one ofu,v. This problem is related to a large variety of identification problems. We investigate the identifying path cover problem in some families of graphs. In particular, we derive the optimal size of an identifying path cover for paths, cycles, hypercubes and topologically irreducible trees and give an upper bound for all trees. We give lower and upper bounds on the minimum size of an identifying path cover for general graphs, and discuss their tightness. In particular, we show that any connected graphGhas an identifying path cover of size at most. We also study the computational complexity of the associated optimization problem, in particular we show that when the length of the paths is asked to be of a fixed value, the problem is APX-complete.
登录
查看更多内容
二分图中的判别代码：界限、极值基数、复杂性
DOI：
10.3934/amc.2008.2.403
发表时间：
2008
期刊：
Adv. Math. Commun.
影响因子：
--
作者：
Emmanuel Charbit;I. Charon;G. Cohen;O. Hudry;A. Lobstein
通讯作者：
A. Lobstein
表征极值有向图以识别邦迪诱导子集定理的代码和极值情况
影响因子：
0.7
作者：
Florent Foucaud;R. Naserasr;Aline Parreau
通讯作者：
Aline Parreau
DOI：
10.37236/934
发表时间：
2007
期刊：
Electron. J. Comb.
影响因子：
--
作者：
I. Charon;I. Honkala;O. Hudry;A. Lobstein
通讯作者：
A. Lobstein
DOI：
10.1016/j.endm.2006.08.005
发表时间：
2006
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
Emmanuel Charbit;I. Charon;G. Cohen;O. Hudry
通讯作者：
O. Hudry
DOI：
10.1016/j.ejc.2011.01.002
发表时间：
2010
期刊：
ArXiv
影响因子：
--
作者：
Florent Foucaud;Eleonora Guerrini;M. Kovse;R. Naserasr;Aline Parreau;Petru Valicov
通讯作者：
Petru Valicov