Even‐hole‐free graphs part II: Recognition algorithm
Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vušković · Journal of Graph Theory · 2002
Abstract 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