IEICE TRANSACTIONS on Fundamentals
Reconfiguration of Steiner Trees in an Unweighted Graph
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.7 pp.1532-1540
- Publication Date
- 2017/07/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.1532
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Haruka MIZUTA
Tohoku University,JST, ERATO, Kawarabayashi Large Graph Project, c/o Global Research Center for Big Data Mathematics
Takehiro ITO
Tohoku University
Xiao ZHOU
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Haruka MIZUTA, Takehiro ITO, Xiao ZHOU, "Reconfiguration of Steiner Trees in an Unweighted Graph" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 7, pp. 1532-1540, July 2017, doi: 10.1587/transfun.E100.A.1532.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1532/_p
Copy
@ARTICLE{e100-a_7_1532,
author={Haruka MIZUTA, Takehiro ITO, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Reconfiguration of Steiner Trees in an Unweighted Graph},
year={2017},
volume={E100-A},
number={7},
pages={1532-1540},
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.},
keywords={},
doi={10.1587/transfun.E100.A.1532},
ISSN={1745-1337},
month={July},}
Copy
TY - JOUR
TI - Reconfiguration of Steiner Trees in an Unweighted Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1532
EP - 1540
AU - Haruka MIZUTA
AU - Takehiro ITO
AU - Xiao ZHOU
PY - 2017
DO - 10.1587/transfun.E100.A.1532
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2017
AB - 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.
ER -
English
