Reconfiguring multiple connected components with size multiset constraints

DOI10.1007/978-981-95-0218-9_6MaRDI QIDQ6866549zbMATH OpenFDO

Authors Yu Nakahata

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-981-95-0218-9_6

zbMATH Keywords

chordal graphcographcombinatorial reconfigurationconnected componentgraph algorithm

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A Linear Recognition Algorithm for Cographs
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Complement reducible graphs
• Complexity of independent set reconfigurability problems
• Independent set reconfiguration in cographs and their generalizations
• Independent set reconfiguration under bounded-hop token jumping
• Introduction to reconfiguration
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• On the Parameterized Complexity for Token Jumping on Graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration of cliques in a graph
• Reconfiguration of dominating sets
• Reconfiguration of regular induced subgraphs
• Reconfiguration on sparse graphs
• Reconfiguration using generalized token jumping
• The complexity of dominating set reconfiguration

Cited in

(1)

• Biclique reconfiguration in bipartite graphs

This page was built for publication: Reconfiguring multiple connected components with size multiset constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866549)