Planar k-Path in Subexponential Time and Polynomial Space

TitlePlanar k-Path in Subexponential Time and Polynomial Space
Publication TypeConference Paper
Year of Publication2011
AuthorsLokshtanov, D., Mnich M., & Saurabh S.
Other Numbers3177
Abstract

In the k-Path problem we are given an n-vertex graph G together with an integer k and asked whether G contains a path of length k as a subgraph. We give the first subexponential time, polynomial space parameterized algorithm for k-Path on planar graphs, and more generally, on H-minor-free graphs.

Bibliographic Notes

Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '11), Teplá-Klášter, Czech Republic

Abbreviated Authors

D. Lokshtanov, M. Mnich, and S. Saurabh

ICSI Research Group

Algorithms

ICSI Publication Type

Article in conference proceedings