Keyword : combinatorial reconfiguration


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(836.5KB)

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(1.2MB)

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(662.8KB)

Reconfiguration of Vertex Covers in a Graph
Takehiro ITO Hiroyuki NOOKA Xiao ZHOU 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2016/03/01
Vol. E99-D  No. 3 ; pp. 598-606
Type of Manuscript:  Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
Category: 
Keyword: 
combinatorial reconfigurationeven-hole-free graphgraph algorithmvertex cover
 Summary | Full Text:PDF(410.2KB)