An exponential time parameterized algorithm for planar disjoint paths

DOI10.1145/3357713.3384250OpenAlexW3035520095MaRDI QIDQ5145014

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

zbMATH Keywords

homologyplanar graphsnetwork flowparameterized complexitydisjoint paths

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ 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