An exponential time parameterized algorithm for planar disjoint paths
From MaRDI portal
Publication:5145014
DOI10.1145/3357713.3384250OpenAlexW3035520095MaRDI QIDQ5145014FDOQ5145014
Meirav Zehavi, Michał Pilipczuk, Pranabendu Misra, Saket Saurabh, Daniel Lokshtanov
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
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
- Publication:3211338
Cited In (8)
- 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
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- A tight lower bound for edge-disjoint paths on planar DAGs
- Finding k Disjoint Paths in a Directed Planar Graph
- Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
- An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
- Parameterized complexity of set-restricted disjoint paths on chordal graphs
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)
