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)
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Chordless paths through three vertices, One-three join: a graph operation and its consequences, The four-in-a-tree problem in triangle-free graphs, Recognizing binet matrices, 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, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, Induced disjoint paths and connected subgraphs for \(H\)-free graphs, MIP formulations for induced graph optimization problems: a tutorial, Perfect forests in graphs and their extensions, Finding a shortest even hole in polynomial time, Large Induced Subgraphs via Triangulations and CMSO, The Induced Disjoint Paths Problem, Exact Solution Algorithms for the Chordless Cycle Problem, Finding induced paths of given parity in claw-free graphs, The \(k\)-in-a-path problem for claw-free graphs, Graphs of large chromatic number, FPT and kernelization algorithms for the induced tree problem, Finding an induced subdivision of a digraph, The three-in-a-tree problem, Algorithms for finding an induced cycle in planar graphs, Unnamed Item, Decomposing Berge graphs and detecting balanced skew partitions, Detecting induced subgraphs, On the mixed set covering, packing and partitioning polytope, A linear algorithm for the group path problem on chordal graphs, Detecting fixed patterns in chordal graphs in polynomial time, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, A faster algorithm for finding minimum Tucker submatrices, Induced disjoint paths problem in a planar digraph, Finding induced trees, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Even-hole-free graphs part I: Decomposition theorem, Few induced disjoint paths for \(H\)-free graphs, Induced Disjoint Paths in Claw-Free Graphs, A structure theorem for graphs with no cycle with a unique chord and its consequences, Polyhedral properties of the induced cluster subgraphs, Recognition of quasi-Meyniel graphs, Unnamed Item, Detecting a long odd hole, Induced packing of odd cycles in planar graphs, Clique or hole in claw-free graphs, Even and odd pairs in comparability and in \(P_4\)-comparability graphs, Attachment centrality: measure for connectivity in networks, Digraphs with all induced directed cycles of the same length are not \(\vec{\chi}\)-bounded, Few induced disjoint paths for \(H\)-free graphs, Unnamed Item, Unnamed Item, A faster algorithm to recognize even-hole-free graphs, Even-hole-free graphs part II: Recognition algorithm
Cites Work
