Reconfiguring spanning and induced subgraphs

Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya, Akira Suzuki, Krishna Vaidyanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
EditorsDaming Zhu, Lusheng Wang
PublisherSpringer Verlag
Pages428-440
Number of pages13
ISBN (Print)9783319947754
DOIs
Publication statusPublished - 2018
Externally publishedYes
Event24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, China
Duration: Jul 2 2018Jul 4 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10976 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Country/TerritoryChina
CityQing Dao
Period7/2/187/4/18

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Reconfiguring spanning and induced subgraphs'. Together they form a unique fingerprint.

Cite this