Complexity of path-forming games

DOI10.1016/0304-3975(93)90357-YzbMath0776.90100OpenAlexW2008003941WikidataQ59568003 ScholiaQ59568003MaRDI QIDQ1210546

Hans L. Bodlaender

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

zbMATH Keywords

graph rewritingcircuitHamiltonian pathgraphs with bounded treewidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Dynamic programming (90C39)

Related Items

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