On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.

DOI10.4230/LIPIcs.STACS.2016.57zbMath1388.68133arXiv1509.05896OpenAlexW2963401228MaRDI QIDQ4601909

Marcin Wrochna, Michał Pilipczuk

Publication date: 24 January 2018

Full work available at URL: https://arxiv.org/abs/1509.05896

zbMATH Keywords

tree decompositiontree-depthLCSNAuxSASavitch's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Internet topics (68M11)

Related Items (5)

Space-Efficient Algorithms for Longest Increasing Subsequence ⋮ Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ Space-efficient algorithms for longest increasing subsequence ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming

This page was built for publication: On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs.