Bounded Tree-Width and LOGCFL

DOI10.1006/jagm.1994.1022zbMath0804.68048OpenAlexW1971056052MaRDI QIDQ4290918

Egon Wanke

Publication date: 5 May 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1022

zbMATH Keywords

decidabilitycomplexity class LOGCFLtree-width bounded graphs

Mathematics Subject Classification ID

Combinatorics on words (68R15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Log-space algorithms for paths and matchings in \(k\)-trees ⋮ The Space Complexity of k-Tree Isomorphism ⋮ An annotated bibliography on guaranteed graph searching ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ Parallel algorithms with optimal speedup for bounded treewidth ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Computing LOGCFL certificates ⋮ Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs

This page was built for publication: Bounded Tree-Width and LOGCFL