Planar k-Path in Subexponential Time and Polynomial Space

Daniel Lokshtanov; Matthias Mnich; Saket Saurabh

doi:10.1007/978-3-642-25870-1_24

Planar k-Path in Subexponential Time and Polynomial Space

Daniel Lokshtanov, Matthias Mnich, Saket Saurabh

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceeding › Academic › peer-review

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. The running time of our algorithm is o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)})o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)}).

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	37th International Workshop, WG 2011 Tepla Monastery, Czech Republic, June 2011 Revised Papers
Editors	Petr Kolman, Jan Kratochvil
Publisher	Springer
Pages	262-270
ISBN (Electronic)	978-3-642-25870-1
ISBN (Print)	978-3-642-25869-5
DOIs	https://doi.org/10.1007/978-3-642-25870-1_24
Publication status	Published - 2011
Externally published	Yes

Publication series

Series	Lecture Notes in Computer Science
Volume	6986

Access to Document

10.1007/978-3-642-25870-1_24

Cite this

Lokshtanov, Daniel ; Mnich, Matthias ; Saurabh, Saket. / Planar k-Path in Subexponential Time and Polynomial Space. Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011 Tepla Monastery, Czech Republic, June 2011 Revised Papers. editor / Petr Kolman ; Jan Kratochvil. Springer, 2011. pp. 262-270 (Lecture Notes in Computer Science, Vol. 6986).

@inproceedings{8bd887c072a14bf198b3cbabe0db8d9b,

title = "Planar k-Path in Subexponential Time and Polynomial Space",

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. The running time of our algorithm is o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)})o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)}).",

author = "Daniel Lokshtanov and Matthias Mnich and Saket Saurabh",

year = "2011",

doi = "10.1007/978-3-642-25870-1_24",

language = "English",

isbn = "978-3-642-25869-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "262--270",

editor = "Petr Kolman and Jan Kratochvil",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "United States",

}

Lokshtanov, D, Mnich, M & Saurabh, S 2011, Planar k-Path in Subexponential Time and Polynomial Space. in P Kolman & J Kratochvil (eds), Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011 Tepla Monastery, Czech Republic, June 2011 Revised Papers. Springer, Lecture Notes in Computer Science, vol. 6986, pp. 262-270. https://doi.org/10.1007/978-3-642-25870-1_24

Planar k-Path in Subexponential Time and Polynomial Space. / Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket.
Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011 Tepla Monastery, Czech Republic, June 2011 Revised Papers. ed. / Petr Kolman; Jan Kratochvil. Springer, 2011. p. 262-270 (Lecture Notes in Computer Science, Vol. 6986).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceeding › Academic › peer-review

TY - GEN

T1 - Planar k-Path in Subexponential Time and Polynomial Space

AU - Lokshtanov, Daniel

AU - Mnich, Matthias

AU - Saurabh, Saket

PY - 2011

Y1 - 2011

N2 - 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. The running time of our algorithm is o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)})o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)}).

AB - 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. The running time of our algorithm is o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)})o(2^{o(\sqrt{k}\log^2 k)}n^{o(1)}).

U2 - 10.1007/978-3-642-25870-1_24

DO - 10.1007/978-3-642-25870-1_24

M3 - Conference article in proceeding

SN - 978-3-642-25869-5

T3 - Lecture Notes in Computer Science

SP - 262

EP - 270

BT - Graph-Theoretic Concepts in Computer Science

A2 - Kolman, Petr

A2 - Kratochvil, Jan

PB - Springer

ER -

Lokshtanov D, Mnich M, Saurabh S. Planar k-Path in Subexponential Time and Polynomial Space. In Kolman P, Kratochvil J, editors, Graph-Theoretic Concepts in Computer Science: 37th International Workshop, WG 2011 Tepla Monastery, Czech Republic, June 2011 Revised Papers. Springer. 2011. p. 262-270. (Lecture Notes in Computer Science, Vol. 6986). doi: 10.1007/978-3-642-25870-1_24