An exponential time parameterized algorithm for planar disjoint paths

DOI10.1145/3357713.3384250MaRDI QIDQ5145014zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, Meirav Zehavi

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

disjoint pathshomologynetwork flowparameterized complexityplanar graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 780786
• A linear-time algorithm for edge-disjoint paths in planar graphs
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• LINEAR-TIME ALGORITHMS FOR DISJOINT TWO-FACE PATHS PROBLEMS IN PLANAR GRAPHS
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• On the complexity of the planar directed edge-disjoint paths problem
• Planar k-path in subexponential time and polynomial space
• Exact algorithms for finding partial edge-disjoint paths
• scientific article; zbMATH DE number 4191702

Cited in

(18)

• Parameterized complexity of set-restricted disjoint paths on chordal graphs
• A tight lower bound for edge-disjoint paths on planar DAGs
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
• Finding k Disjoint Paths in a Directed Planar Graph
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Shortest two disjoint paths in conservative graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Shortest two disjoint paths in conservative graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Lower bounds for approximate (\& exact) \(k\)-\textsc{Disjoint-Shortest-Paths}
• Exploiting dense structures in parameterized complexity
• The Even-Path problem in directed single-crossing-minor-free graphs
• Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
• Does subset sum admit short proofs?
• The parameterized complexity of coordinated motion planning

This page was built for publication: An exponential time parameterized algorithm for planar disjoint paths

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