Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
From MaRDI portal
Publication:6647761
DOI10.1016/j.ic.2024.105227MaRDI QIDQ6647761
Publication date: 3 December 2024
Published in: Information and Computation (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower and upper bounds for long induced paths in 3-connected planar graphs
- The disjoint paths problem in quadratic time
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- The three-in-a-tree problem
- Chordless paths through three vertices
- The strong perfect graph theorem
- Detecting holes and antiholes in graphs
- Even pairs in Berge graphs
- A new property of critical imperfect graphs and some consequences
- On the complexity of testing for odd holes and induced odd paths
- Witnesses for Boolean matrix multiplication and for transitive closure
- The complexity of induced minors and related problems
- Path parity and perfection
- Graph minors. XIII: The disjoint paths problem
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
- Finding and listing induced paths and cycles
- Finding an induced path that is not a shortest path
- Detecting a long odd hole
- Induced disjoint paths in AT-free graphs
- Detecting a long even hole
- Mim-width. I. Induced path problems
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- A faster algorithm to recognize even-hole-free graphs
- Recognizing Berge graphs
- Induced paths in 5-connected graphs
- Even-hole-free graphs. I: Decomposition theorem
- Even-hole-free graphs part II: Recognition algorithm
- Colouring square-free graphs without long induced paths.
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Powers of tensors and fast matrix multiplication
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Transformations which Preserve Perfectness and H-Perfectness of Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Finding the k Shortest Paths
- Even and odd holes in cap-free graphs
- Finding Even Cycles Even Faster
- Color-coding
- Odd Holes in Bull-Free Graphs
- Detecting even holes
- The NP-completeness column
- Finding even cycles faster via capped k-walks
- Finding a Shortest Odd Hole
- Detecting an Odd Hole
- Three-in-a-tree in near linear time
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Multiplying matrices faster than coppersmith-winograd
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Odd Hole Recognition in Graphs of Bounded Clique Size
- On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
- Finding a shortest even hole in polynomial time
- Detours in directed graphs
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- Graphs with all holes the same length
- A refined laser method and faster matrix multiplication
- New bounds for matrix multiplication: from alpha to omega
This page was built for publication: Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
