Paper Info
Title
Reconfiguration Of Steiner Trees In An Unweighted Graph
Abstract
We study a reconfiguration problem for Steiner trees in an unweighted graph, which determines whether there exists a sequence of Steiner trees that transforms a given Steiner tree into another one by exchanging a single edge at a time. In this paper, we show that the problem is PSPACE-complete even for split graphs, while solvable in linear time for interval graphs and for cographs.
Year
DOI
Venue
2017
10.1587/transfun.E100.A.1532
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
DocType
Volume
cograph, combinatorial reconfiguration, interval graph, PSPACE-complete, split graph, Steiner tree
Journal
E100A
Issue
ISSN
Citations 
7
0916-8508
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Haruka Mizuta121.46
Takehiro Ito226040.71
Xiao Zhou332543.69