Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
From MaRDI portal
Cites work
- A faster algorithm to recognize even-hole-free graphs
- A new property of critical imperfect graphs and some consequences
- 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
- Color-coding
- Colouring square-free graphs without long induced paths
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Detecting a long even hole
- Detecting a long odd hole
- Detecting an Odd Hole
- Detecting even holes
- Detecting holes and antiholes in graphs
- Detours in directed 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
- Finding a shortest even hole in polynomial time
- Finding a Shortest Odd Hole
- 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
- 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 1256679 (Why is no real title available?)
- scientific article; zbMATH DE number 7788454 (Why is no real title available?)
- Induced paths in 5-connected graphs
- Lower and upper bounds for long induced paths in 3-connected planar graphs
- Mim-width. I. Induced path problems
- 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 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
- Path parity and perfection
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Powers of tensors and fast matrix multiplication
- Recognizing Berge graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- The complexity of induced minors and related problems
- The disjoint paths problem in quadratic time
- The NP-completeness column
- 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
- Witnesses for Boolean matrix multiplication and for transitive closure
This page was built for publication: Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6647761)
