On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs

DOI10.1145/3154856zbMath1427.68130OpenAlexW2783306705MaRDI QIDQ4973895

Marcin Wrochna, Michał Pilipczuk

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5758/

zbMATH Keywords

completenesstreewidthpathwidthCSPtime-space tradeoffcomplexity theorycomplexity classestree-depthLCS

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Improved Bounds for Centered Colorings

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