Reconfiguration of Steiner Trees in an Unweighted Graph

Autor:	Takehiro Ito, Haruka Mizuta, Xiao Zhou
Rok vydání:	2016
Předmět:	Sequence Existential quantification Control reconfiguration 0102 computer and information sciences 02 engineering and technology Computer Science::Computational Geometry 01 natural sciences Steiner tree problem Combinatorics symbols.namesake 010201 computation theory & mathematics Chordal graph TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY 0202 electrical engineering electronic engineering information engineering symbols Interval (graph theory) 020201 artificial intelligence & image processing Enhanced Data Rates for GSM Evolution Computer Science::Data Structures and Algorithms Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319445427 IWOCA
DOI:	10.1007/978-3-319-44543-4_13
Popis:	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 (and hence for chordal graphs), while solvable in linear time for interval graphs.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b12bb3b3043f4d16db44decf9af83578 https://doi.org/10.1007/978-3-319-44543-4_13 Zobrazit plný text záznamu