Bounded tree-width and LOGCFL
From MaRDI portal
Publication:6184391
DOI10.1007/3-540-57899-4_39zbMath1528.68329OpenAlexW1540780972MaRDI QIDQ6184391
Publication date: 5 January 2024
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-57899-4_39
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)
Cites Work
- Unnamed Item
- Unnamed Item
- Tree-size bounded alternation
- Algorithms for graph problems on BNLC structured garphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Languages that Capture Complexity Classes
- Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
- Two Applications of Inductive Counting for Complementation Problems
- Alternation
- On the Tape Complexity of Deterministic Context-Free Languages
- A linear time algorithm for finding tree-decompositions of small treewidth
- Efficient decision procedures for graph properties on context-free graph languages
This page was built for publication: Bounded tree-width and LOGCFL
