2019-11-14T02:18:58Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001640412018-03-30T07:23:32Z01164:02592:08452:08750
Reachability between Steiner Trees in a GraphReachability between Steiner Trees in a Graphenghttp://id.nii.ac.jp/1001/00164007/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=164041&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Information Processing Society of JapanGraduate School of Information Sciences, Tohoku University／JST, ERATO, Kawarabayashi Large Graph Project, c/o Global Research Center for Big Data Mathematics／NIIGraduate School of Information Sciences, Tohoku University／CREST, JSTGraduate School of Information Sciences, Tohoku UniversityHaruka, MizutaTakehiro, ItoXiao, ZhouIn this paper, we study the reachability between Steiner trees in a graph: Given two Steiner trees of an unweighted graph, we wish to transform one into the other via Steiner trees by exchanging a single edge at a time. This decision problem is PSPACE-complete in general. In this paper, we give a linear-time algorithm to solve the problem when restricted to interval graphs.In this paper, we study the reachability between Steiner trees in a graph: Given two Steiner trees of an unweighted graph, we wish to transform one into the other via Steiner trees by exchanging a single edge at a time. This decision problem is PSPACE-complete in general. In this paper, we give a linear-time algorithm to solve the problem when restricted to interval graphs.AN1009593X研究報告アルゴリズム（AL）2016-AL-15816152016-06-172188-85662016-06-13