文章基本信息

标题：Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
本地全文：下载
作者：Haruka Mizuta ; Tatsuhiko Hatanaka ; Takehiro Ito 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-11
DOI：10.4230/LIPIcs.MFCS.2019.79
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper, we study the problem of deciding if there is a transformation between two given minimum Steiner trees of an unweighted graph such that each transformation step respects a prescribed reconfiguration rule and results in another minimum Steiner tree of the graph. We consider two reconfiguration rules, both of which exchange a single vertex at a time, and generalize the known reconfiguration problem for shortest paths in an unweighted graph. This generalization implies that our problems under both reconfiguration rules are PSPACE-complete for bipartite graphs. We thus study the problems with respect to graph classes, and give some boundaries between the polynomial-time solvable and PSPACE-complete cases.
关键词：Combinatorial reconfiguration; Graph algorithms; Steiner tree