Reconfiguration of regular induced subgraphs

DOI10.1007/978-3-030-96731-4_4OpenAlexW3217382229MaRDI QIDQ2154077

Yota Otachi, Takehiro Ito, Hiroshi Eto, Yasuaki Kobayashi, Kunihiro Wasa

Publication date: 13 July 2022

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

zbMATH Keywords

computational complexityregular induced subgraphcombinatorial reconfiguration

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• The complexity of rerouting shortest paths
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Complexity of independent set reconfigurability problems
• On the complexity of reconfiguration problems
• Reconfiguration in bounded bandwidth and tree-depth
• On girth and the parameterized complexity of token sliding and Token Jumping
• Token sliding on split graphs
• Parameterized complexity of independent set reconfiguration problems
• Introduction to reconfiguration
• Independent Set Reconfiguration in Cographs and their Generalizations
• The complexity of change
• Degree-Constrained Subgraph Reconfiguration is in P
• Reconfiguration of Cliques in a Graph
• Reconfiguring Independent Sets in Claw-Free Graphs
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs
• Reconfiguring spanning and induced subgraphs