Large-Girth Roots of Graphs
Large-Girth Roots of Graphs
复制标题
图的大周根
DOI：
10.1137/100792949
复制
发表时间：
2010
影响因子：
0.8
通讯作者：
Adamaszek A
中科院分区：
文献类型：
--
作者：
Adamaszek A
本文研究了图的幂的识别和根的计算问题。我们的重点是类图没有短周期。本文给出了围长至少为r的图的r次方的多项式时间识别算法，从而改进了最近提出的一个界。我们的算法还找到了给定图的所有r次根，这些根的围长至少为1度，没有1个顶点，这是Levenshtein [Discrete Math.，308（2008），pp. 993-998]这样的根应该是唯一的。到目前为止，类似的算法只针对。在消极的一面，我们证明了识别图的权力成为一个NP-完全问题时，围长的界限是约两倍小。(Anna Adamaszek的正确隶属关系是计算机科学系和离散数学及其应用中心（DIMAP），沃里克大学，考文垂，CV 4 7AL，英国。
We study the problem of recognizing graph powers and computing roots of graphs. Our focus is on classes of graphs with no short cycles. We provide a polynomial time recognition algorithm forr-th powers of graphs of girth at least, thus improving a recently conjectured bound. Our algorithm also finds allr-th roots of a given graph that have girth at leastand no degree one vertices, which is a step toward a recent conjecture of Levenshtein [Discrete Math., 308 (2008), pp. 993–998] that such roots should be unique. Similar algorithms have so far been designed only for. On the negative side, we prove that recognition of graph powers becomes an NP-complete problem when the bound on girth is about twice smaller. (Anna Adamaszek's correct affiliation is Department of Computer Science and Centre for Discrete Mathematics and Its Applications (DIMAP), University of Warwick, Coventry, CV4 7AL, UK.)
登录
查看更多内容
DOI：
10.1016/j.disc.2007.09.027
发表时间：
2008
期刊：
Discret. Math.
影响因子：
--
作者：
V. Levenshtein
通讯作者：
V. Levenshtein
DOI：
10.1137/s089548019120016x
发表时间：
1991
期刊：
ArXiv
影响因子：
--
作者：
Yaw;S. Skiena
通讯作者：
S. Skiena
影响因子：
1.1
作者：
Kutz, M
通讯作者：
Kutz, M
n 路径图和具有 n 次根的图的表征
DOI：
10.1016/0095-8956(74)90074-4
发表时间：
1974
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
F. Escalante;L. Montejano;T. Rojano
通讯作者：
T. Rojano
从图的顶点的 2 邻域重建图
DOI：
10.1016/j.dam.2006.11.016
发表时间：
2008
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
V. Levenshtein;E. Konstantinova;E. Konstantinov;S. Molodtsov
通讯作者：
S. Molodtsov