Shortest k-disjoint paths via determinants

DOI10.4230/LIPICS.FSTTCS.2018.19MaRDI QIDQ5090955zbMATH OpenFDO

Authors Samir Datta, Siddharth Iyer, Raghav Kulkarni, A. Mukherjee

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1802.01338

zbMATH Keywords

parallel algorithmdeterminantplanar graphdisjoint pathscycle coverinclusion-exclusion

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm
• The Directed Disjoint Shortest Paths Problem
• On shortest disjoint paths in planar graphs
• Shortest two disjoint paths in polynomial time
• Shortest two disjoint paths in polynomial time

Cites work

• scientific article; zbMATH DE number 432791 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• Almost polynomial hardness of node-disjoint paths in grids
• Fast Parallel Matrix Inversion Algorithms
• Finding k Disjoint Paths in a Directed Planar Graph
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XIII: The disjoint paths problem
• Graphs of non-crossing perfect matchings
• Improved approximation for node-disjoint paths in planar graphs
• Length-bounded disjoint paths in planar graphs
• Matching is as easy as matrix inversion
• New hardness results for routing on disjoint paths
• On shortest disjoint paths in planar graphs
• On the Computational Complexity of Combinatorial Problems
• On the complexity of the disjoint paths problem
• On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary
• Planarity testing revisited
• Resolution of Hartmanis' conjecture for NL-hard sparse sets
• Shortest two disjoint paths in polynomial time
• Shortest vertex-disjoint two-face paths in planar graphs
• The complexity of planarity testing
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• Towards single face shortest vertex-disjoint paths in undirected planar graphs

Cited in

(4)

• The widestk-set of disjoint paths problem
• Shortest two disjoint paths in polynomial time
• scientific article; zbMATH DE number 1305420 (Why is no real title available?)
• Faster 2-Disjoint-Shortest-Paths Algorithm

This page was built for publication: Shortest \(k\)-disjoint paths via determinants

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