Improved algorithms for perfect graphs and odd holes

Cites work

\(K_{4}\)-free graphs with no odd hole: even pairs and the circular chromatic number
\(K_{4}\)-free graphs with no odd holes
A faster algorithm to recognize even-hole-free graphs
A new property of critical imperfect graphs and some consequences
A polynomial algorithm for recognizing perfect graphs
A refined laser method and faster matrix multiplication
Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
Algorithmic Aspects of Vertex Elimination on Graphs
Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
Chordless paths through three vertices
Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions
Clique-coloring some classes of odd-hole-free graphs
Color-coding
Coloring the Maximal Cliques of Graphs
Colouring square-free graphs without long induced paths
Complexity of clique-coloring odd-hole-free graphs
Computing the girth of a planar graph in O(n n) time
Computing the girth of a planar graph in linear time
Counting small induced subgraphs with hereditary properties
Decomposing and clique-coloring (diamond, odd-hole)-free graphs
Decomposition of even-hole-free graphs with star cutsets and 2-joins
Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
Detecting a long even hole
Detecting a long odd hole
Detecting an Odd Hole
Detecting even holes
Detecting holes and antiholes in graphs
Even and odd holes in cap-free graphs
Even pairs in Berge graphs
Even-hole-free graphs part II: Recognition algorithm
Even-hole-free graphs. I: Decomposition theorem
Even-hole-free graphs: A survey
Faster matrix multiplication via asymmetric hashing
Finding a Minimum Circuit in a Graph
Finding a shortest even hole in polynomial time
Finding a Shortest Odd Hole
Finding a smallest odd hole in a claw-free graph using global structure
Finding an even hole in a graph
Finding an induced path of given parity in planar graphs in polynomial time
Finding an induced path that is not a shortest path
Finding and listing induced paths and cycles
Finding Even Cycles Even Faster
Finding even cycles faster via capped k-walks
Finding the k Shortest Paths
Graph minors. XIII: The disjoint paths problem
Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
Graphs with all holes the same length
Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
scientific article; zbMATH DE number 1670873 (Why is no real title available?)
scientific article; zbMATH DE number 3889583 (Why is no real title available?)
scientific article; zbMATH DE number 3168327 (Why is no real title available?)
scientific article; zbMATH DE number 3902654 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 7788454 (Why is no real title available?)
Induced cycles and paths are harder than you think
Induced disjoint paths in AT-free graphs
Induced disjoint paths in AT-free graphs
Induced odd cycle packing number, independent sets, and chromatic number
Induced packing of odd cycles in planar graphs
Induced paths in 5-connected graphs
Induced subgraphs of graphs with large chromatic number. I. Odd holes
Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
Lower and upper bounds for long induced paths in 3-connected planar graphs
Mim-width. I. Induced path problems
Modularity of cycles and paths in graphs
Multiplying matrices faster than coppersmith-winograd
New bounds for matrix multiplication: from alpha to omega
Odd Hole Recognition in Graphs of Bounded Clique Size
Odd holes in bull-free graphs
On circular-perfect graphs: a survey
On some graph classes related to perfect graphs: a survey
On the complexity of finding large odd induced subgraphs and odd colorings
On the complexity of testing for odd holes and induced odd paths
On the maximum weight independent set problem in graphs without induced cycles of length at least five
On the structure of (banner, odd hole)-free graphs
Path parity and perfection
Perfect graphs
Permanents, Pfaffian orientations, and even directed circuits
Powers of tensors and fast matrix multiplication
Pólya's permanent problem
Recognizing Berge graphs
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
Smallest odd holes in claw-free graphs (extended abstract)
Subcubic equivalences between path, matrix, and triangle problems
The (theta, wheel)-free graphs. IV: Induced paths and cycles
The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
The disjoint paths problem in quadratic time
The NP-completeness column
The parameterised complexity of counting even and odd induced subgraphs
The shortest even cycle problem is tractable
The strong perfect graph theorem
The three-in-a-tree problem
Three-in-a-tree in near linear time
Transformations which Preserve Perfectness and H-Perfectness of Graphs

This page was built for publication: Improved algorithms for perfect graphs and odd holes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7262282)