Keyword : PSPACE-complete


The Coloring Reconfiguration Problem on Specific Graph Classes
Tatsuhiko HATANAKA Takehiro ITO Xiao ZHOU 
Publication:   
Publication Date: 2019/03/01
Vol. E102-D  No. 3 ; pp. 423-429
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
chordal graphscombinatorial reconfigurationgraph algorithmgraph coloringPSPACE-complete
 Summary | Full Text:PDF

The Complexity of Induced Tree Reconfiguration Problems
Kunihiro WASA Katsuhisa YAMANAKA Hiroki ARIMURA 
Publication:   
Publication Date: 2019/03/01
Vol. E102-D  No. 3 ; pp. 464-469
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
Category: 
Keyword: 
reconfiguration probleminduced treesPSPACE-completeW[1]-hardFPT
 Summary | Full Text:PDF

The Complexity of (List) Edge-Coloring Reconfiguration Problem
Hiroki OSAWA Akira SUZUKI Takehiro ITO Xiao ZHOU 
Publication:   
Publication Date: 2018/01/01
Vol. E101-A  No. 1 ; pp. 232-238
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
combinatorial reconfigurationedge-coloringplanar graphPSPACE-complete
 Summary | Full Text:PDF

Reconfiguration of Steiner Trees in an Unweighted Graph
Haruka MIZUTA Takehiro ITO Xiao ZHOU 
Publication:   
Publication Date: 2017/07/01
Vol. E100-A  No. 7 ; pp. 1532-1540
Type of Manuscript:  PAPER
Category: Algorithms and Data Structures
Keyword: 
cographcombinatorial reconfigurationinterval graphPSPACE-completesplit graphSteiner tree
 Summary | Full Text:PDF

Computational Complexity of Predicting Periodicity in the Models of Lorentz Lattice Gas Cellular Automata
Takeo HAGIWARA Tatsuie TSUKIJI Zhi-Zhong CHEN 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/06/01
Vol. E99-A  No. 6 ; pp. 1034-1049
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
cellular automatacomputational complexityLorentz lattice gasLangton's antPSPACE-complete
 Summary | Full Text:PDF

The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
Tatsuhiko HATANAKA Takehiro ITO Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2015/06/01
Vol. E98-A  No. 6 ; pp. 1168-1178
Type of Manuscript:  Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph algorithmlist coloringpathwidthPSPACE-completereachability on solution spacereconfiguration
 Summary | Full Text:PDF

Generalized Chat Noir is PSPACE-Complete
Chuzo IWAMOTO Yuta MUKAI Yuichi SUMIDA Kenichi MORITA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2013/03/01
Vol. E96-D  No. 3 ; pp. 502-505
Type of Manuscript:  Special Section LETTER (Special Section on Foundations of Computer Science — New Trends in Algorithms and Theory of Computation —)
Category: 
Keyword: 
PSPACE-completecomputational complexitytwo-player gameChat Noir
 Summary | Full Text:PDF

Shrinking Alternating Two-Pushdown Automata
Friedrich OTTO Etsuro MORIYA 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/04/01
Vol. E87-D  No. 4 ; pp. 959-966
Type of Manuscript:  PAPER
Category: Automata and Formal Language Theory
Keyword: 
shrinkingalternatingtwo-pushdown automatonPSPACE-complete
 Summary | Full Text:PDF