Bounded Tree-Width and LOGCFL

DOI10.1006/JAGM.1994.1022MaRDI QIDQ4290918zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(13)

• Computing LOGCFL certificates
• An annotated bibliography on guaranteed graph searching
• Parallel algorithms with optimal speedup for bounded treewidth
• 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)