Reconfiguration of Steiner Trees in an Unweighted Graph

Haruka MIZUTA; Takehiro ITO; Xiao ZHOU

doi:10.1587/transfun.E100.A.1532

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

Online ISSN : 1745-1337
Print ISSN : 0916-8508

Regular Section

Reconfiguration of Steiner Trees in an Unweighted Graph

Haruka MIZUTA, Takehiro ITO, Xiao ZHOU

Author information

Keywords: cograph, combinatorial reconfiguration, interval graph, PSPACE-complete, split graph, Steiner tree

JOURNAL RESTRICTED ACCESS

2017 Volume E100.A Issue 7 Pages 1532-1540

DOI https://doi.org/10.1587/transfun.E100.A.1532

Details

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.

Content from these authors

Favorites & Alerts

Corresponding author