Planar k-Path in Subexponential Time and Polynomial Space

DOI10.1007/978-3-642-25870-1_24zbMath1341.05044OpenAlexW118014313MaRDI QIDQ3104782

Saket Saurabh, Matthias Mnich, Daniel Lokshtanov

Publication date: 16 December 2011

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25870-1_24

zbMATH Keywords

\(H\)-minor-free graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Space saving by dynamic algebraization based on tree-depth ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Approximate Counting of k-Paths: Deterministic and in Polynomial Space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Catalan structures and dynamic programming in \(H\)-minor-free graphs
• Subexponential parameterized algorithms
• On problems without polynomial kernels
• Highly connected sets and the excluded grid theorem
• Treewidth. Computations and approximations
• Graph separators: A parameterized view
• Saving space by algebraization
• Subexponential Algorithms for Partial Cover Problems
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Faster Steiner Tree Computation in Polynomial-Space
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• (Meta) Kernelization
• Parameterized and Exact Computation
• Bidimensionality and Geometric Graphs
• Algorithms – ESA 2005

This page was built for publication: Planar k-Path in Subexponential Time and Polynomial Space