Bounded Tree-Width and LOGCFL

DOI10.1006/JAGM.1994.1022zbMATH Open0804.68048OpenAlexW1971056052MaRDI QIDQ4290918FDOQ4290918

Authors: 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

Recommendations

• Computing LOGCFL certificates
• Canonizing graphs of bounded tree width in logspace
• Canonizing Graphs of Bounded Tree Width in Logspace
• scientific article; zbMATH DE number 4210186

zbMATH Keywords

decidabilitycomplexity class LOGCFLtree-width bounded graphs

Mathematics Subject Classification ID

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

Cited In (13)

• Computing LOGCFL certificates
• Parallel algorithms with optimal speedup for bounded treewidth
• An annotated bibliography on guaranteed graph searching
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• The isomorphism problem for \(k\)-trees is complete for logspace
• Graphs of bounded treewidth can be canonized in AC\(^1\)
• Properties that characterize LOGCFL
• Lower Bounds for QBFs of Bounded Treewidth
• Default logic and bounded treewidth
• Canonizing Graphs of Bounded Tree Width in Logspace
• Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
• Log-space algorithms for paths and matchings in \(k\)-trees
• The Space Complexity of k-Tree Isomorphism

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4290918)