Algorithms for Square Roots of Graphs
Algorithms for Square Roots of Graphs
复制标题
图的平方根算法
DOI：
10.1137/s089548019120016x
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
S. Skiena
中科院分区：
文献类型：
--
作者：
Yaw;S. Skiena
一个图G =（V，E）$的n次幂（$n \geq 1$），记作$G^n$，定义为以V$为顶点集，且两个顶点u，v$在$G^n$中相邻的图当且仅当它们之间存在一条长度不超过$n$的路。类似地，如果$G^n = H$，则图$H$有$n$次根$G$。对于n = 2的情况，我们说G^2是G的平方，G是G^2的平方根。本文给出了求给定图的树平方根的线性时间算法和求平面图的平方根的线性时间算法。本文还给出了求细分图平方根的多项式时间算法，它等价于求全图的求逆问题。在此基础上，给出了求三次图中Hamilton圈的线性时间算法，并证明了求图的最大幂团的NP完全性和树的幂的弦性.
The $n$th power ($n \geq 1$) of a graph $G = (V, E)$, written $G^n$, is defined to be the graph having $V$ as its vertex set with two vertices $u, v$ adjacent in $G^n$ if and only if there exists a path of length at most $n$ between them. Similarly, graph $H$ has an $n$th root $G$ if $G^n = H$. For the case of $n = 2$, we say that $G^2$ is the square of $G$ and $G$ is the square root of $G^2$. This paper presents a linear time algorithm for finding the tree square roots of a given graph and a linear time algorithm for finding the square roots of planar graphs. A polynomial time algorithm for finding the square roots of subdivision graphs, which is equivalent to the problem of the inversion of total graphs, is also presented. Further, the authors give a linear time algorithm for finding a Hamiltonian cycle in a cubic graph and prove the NP-completeness of finding the maximum cliques in powers of graphs and the chordality of powers of trees.