Complexity of path-forming games
From MaRDI portal
Publication:1210546
DOI10.1016/0304-3975(93)90357-YzbMath0776.90100OpenAlexW2008003941WikidataQ59568003 ScholiaQ59568003MaRDI QIDQ1210546
Publication date: 30 August 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90357-y
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Dynamic programming (90C39)
Related Items (13)
On the computational complexities of various geography variants ⋮ Games, Puzzles and Treewidth ⋮ On variants of vertex geography on undirected graphs ⋮ The complexity of mean payoff games on graphs ⋮ The shortest connection game ⋮ Games on interval and permutation graph representations ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Undirected edge geography ⋮ Geography ⋮ On the shortest path game ⋮ Playing weighted Tron on trees ⋮ All structured programs have small tree width and good register allocation ⋮ A partial k-arboretum of graphs with bounded treewidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- PSPACE-Hardness of some combinatorial games
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Computing a perfect strategy for nxn chess requires time exponential in n
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Geography
- On the complexity of some two-person perfect-information games
- Graph minors. XIII: The disjoint paths problem
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Algorithms finding tree-decompositions of graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- N by N Checkers is Exptime Complete
- Easy problems for tree-decomposable graphs
- Characterization and Recognition of Partial 3-Trees
- The NP-completeness column: an ongoing guide
- Alternation with restrictions on looping
- Complexity of Finding Embeddings in a k-Tree
- Some combinatorial game problems require Ω( n k ) time
- Efficient algorithms for finding minimum spanning forests of hierarchically defined graphs
- Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
- Provably Difficult Combinatorial Games
- GO Is Polynomial-Space Hard
- ON THE COMPLEXITY OF SOME COLORING GAMES
- A Combinatorial Problem Which Is Complete in Polynomial Space
- Linear-time computation of optimal subgraphs of decomposable graphs
- The complexity of satisfiability problems
- The NP-completeness column: An ongoing guide
This page was built for publication: Complexity of path-forming games