TY - GEN
T1 - Reconfiguring spanning and induced subgraphs
AU - Hanaka, Tesshu
AU - Ito, Takehiro
AU - Mizuta, Haruka
AU - Moore, Benjamin
AU - Nishimura, Naomi
AU - Subramanya, Vijay
AU - Suzuki, Akira
AU - Vaidyanathan, Krishna
N1 - Funding Information:
This work is partially supported by JST ERATO Grant Number JPMJER1201, JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP16K00004 and JP17K12636, Japan. Research by Canadian authors is supported by the Natural Science and Engineering Research Council of Canada.
Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties.
AB - Subgraph reconfiguration is a family of problems focusing on the reachability of the solution space in which feasible solutions are subgraphs, represented either as sets of vertices or sets of edges, satisfying a prescribed graph structure property. Although there has been previous work that can be categorized as subgraph reconfiguration, most of the related results appear under the name of the property under consideration; for example, independent set, clique, and matching. In this paper, we systematically clarify the complexity status of subgraph reconfiguration with respect to graph structure properties.
UR - http://www.scopus.com/inward/record.url?scp=85049683644&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049683644&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-94776-1_36
DO - 10.1007/978-3-319-94776-1_36
M3 - Conference contribution
AN - SCOPUS:85049683644
SN - 9783319947754
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 428
EP - 440
BT - Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
A2 - Zhu, Daming
A2 - Wang, Lusheng
PB - Springer Verlag
T2 - 24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Y2 - 2 July 2018 through 4 July 2018
ER -