Reconfiguring spanning and induced subgraphs

DOI10.1007/978-3-319-94776-1_36zbMath1436.68136arXiv1803.06074OpenAlexW2964327015MaRDI QIDQ5916255

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

Publication date: 4 October 2018

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.06074

zbMATH Keywords

graph algorithmcombinatorial reconfiguration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Reconfiguration of regular induced subgraphs ⋮ Reconfiguring (non-spanning) arborescences ⋮ Reconfiguration of time-respecting arborescences ⋮ Unnamed Item ⋮ Reconfiguring directed trees in a digraph ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Reconfiguring spanning and induced subgraphs ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of rerouting shortest paths
• Complexity of independent set reconfigurability problems
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Token jumping in minor-closed classes
• Reconfiguration in bounded bandwidth and tree-depth
• Introduction to reconfiguration
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Degree-Constrained Subgraph Reconfiguration is in P
• Reconfiguration of Cliques in a Graph
• Reconfiguring spanning and induced subgraphs

This page was built for publication: Reconfiguring spanning and induced subgraphs