Premium
Even‐hole‐free graphs part II: Recognition algorithm
Author(s) -
Conforti Michele,
Cornuéjols Gérard,
Kapoor Ajai,
Vušković Kristina
Publication year - 2002
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10045
Subject(s) - mathematics , combinatorics , graph , discrete mathematics , algorithm
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom