Carnegie Mellon University
Browse

Even-Hole-Free Graphs Part II: Recognition Algorithm

Download (3.48 MB)
journal contribution
posted on 1963-01-01, 00:00 authored by Michele Conforti, Gerard CornuejolsGerard Cornuejols, Ajai Kapoor, Kristina Vušković
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.

History

Date

1963-01-01

Usage metrics

    Categories

    Keywords

    even holepolynomial algorithmdecompositionBusiness and Management not elsewhere classified

    Licence

    In Copyright

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC