Even‐hole‐free graphs part II: Recognition algorithm
Even‐hole‐free graphs part II: Recognition algorithm
复制标题
无偶孔图第二部分：识别算法
DOI：
10.1002/jgt.10045
复制
发表时间：
2002
影响因子：
0.9
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
M. Conforti;G. Cornuéjols;Ajai Kapoor;Kristina Vuskovic
我们提出了一个算法，确定在polytime图是否包含一个甚至洞。该算法基于在本工作的第一部分中获得的无偶洞图的分解定理。我们还给出了一个多时间算法，以找到一个图中的偶洞时，一个存在。© 2002 Wiley Periodicals，Inc. J Graph Theory 40：238-266，2002
We present an algorithm that determines in polytime whether a graph contains an even hole. The algorithm is based on a decomposition theorem for even‐hole‐free graphs obtained in Part I of this work. We also give a polytime algorithm to find an even hole in a graph when one exists. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 238–266, 2002