Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm

DOI10.4230/LIPICS.ISAAC.2018.19MaRDI QIDQ5091009zbMATH OpenFDO

Authors Andreas Björklund, Thore Husfeldt

Publication date 21 July 2022

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

zbMATH Keywords

cubic planar graphshortest disjoint paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Shortest k-disjoint paths via determinants
• Shortest two disjoint paths in polynomial time
• Shortest two disjoint paths in polynomial time
• On shortest disjoint paths in planar graphs
• On shortest disjoint paths in planar graphs

Cites work

• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• A taxonomy of problems with fast parallel algorithms
• An efficient parallel algorithm for planarity
• Disjoint paths in graphs
• Fast Parallel Matrix Inversion Algorithms
• Generalized Nested Dissection
• scientific article; zbMATH DE number 3725714 (Why is no real title available?)
• scientific article; zbMATH DE number 3517179 (Why is no real title available?)
• scientific article; zbMATH DE number 1151367 (Why is no real title available?)
• Matching is as easy as matrix inversion
• Matching theory
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• Modern computer algebra
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• On computing the determinant in small parallel time using a small number of processors
• On shortest disjoint paths in planar graphs
• On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
• Optimization via enumeration: A new algorithm for the max cut problem
• Planar disjoint-paths completion
• Planar graph perfect matching is in NC
• Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph
• Shortest \((A+B)\)-path packing via hafnian
• Shortest two disjoint paths in polynomial time
• Shortest vertex-disjoint two-face paths in planar graphs
• Solving the 2-disjoint paths problem in nearly linear time
• The complexity of counting in sparse, regular, and planar graphs
• Tree metrics and edge-disjoint \(S\)-paths

Cited in

(4)

• Faster 2-Disjoint-Shortest-Paths Algorithm
• Shortest k-disjoint paths via determinants
• Shortest two disjoint paths in polynomial time
• Using a geometric Lens to find k disjoint shortest paths

This page was built for publication: Counting shortest two disjoint paths in cubic planar graphs with an NC algorithm

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