On the complexity of testing for odd holes and induced odd paths
From MaRDI portal
Publication:1175980
DOI10.1016/0012-365X(91)90098-MzbMath0753.05046MaRDI QIDQ1175980
Publication date: 25 June 1992
Published in: Discrete Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Recognition of quasi-Meyniel graphs, A linear algorithm for the group path problem on chordal graphs, Chordless paths through three vertices, Even and odd pairs in comparability and in \(P_4\)-comparability graphs, Path parity and perfection, A polynomial algorithm for the parity path problem on perfectly orientable graphs, The parity path problem on some subclasses of perfect graphs, Decomposing Berge graphs and detecting balanced skew partitions, Even-hole-free graphs part I: Decomposition theorem, Even-hole-free graphs part II: Recognition algorithm, The Induced Disjoint Paths Problem
Cites Work