Even‐hole‐free graphs part I: Decomposition theorem
Even‐hole‐free graphs part I: Decomposition theorem
复制标题
无偶孔图第一部分：分解定理
DOI：
10.1002/jgt.10006
复制
发表时间：
2002
影响因子：
0.9
通讯作者：
Kristina Vuskovic
中科院分区：
文献类型：
--
作者：
M. Conforti;G. Cornuéjols;Ajai Kapoor;Kristina Vuskovic
证明了偶孔无图的一个分解定理。使用的分解是2 -连接和星形，双星和三星切割集。本文的第二部分利用这个定理得到了偶孔无图的多时识别算法。©2002约翰威利父子公司[J] .图论学报（自然科学版），2002
We prove a decomposition theorem for even‐hole‐free graphs. The decompositions used are 2‐joins and star, double‐star and triple‐star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even‐hole‐free graphs. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 6–49, 2002