The shortest path reconfiguration problem based on relaxation of reconfiguration rules

DOI10.1007/978-981-97-0566-5_17MaRDI QIDQ6575398zbMATH OpenFDO

Authors Naoki Domon, Akira Suzuki, Yuma Tamura, Xiao Zhou

Publication date 19 July 2024

Full work available at URL https://doi.org/10.1007/978-981-97-0566-5_17

zbMATH Keywords

graph algorithmparameterized complexityreconfiguration problemshortest path

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Reconfiguration graphs of shortest paths
• Reconfiguration in bounded bandwidth and tree-depth
• Relationships between nondeterministic and deterministic tape complexities
• Rerouting shortest paths in planar graphs
• Shortest paths between shortest paths
• Solving MAX-\(r\)-SAT above a tight lower bound
• The complexity of change
• The complexity of rerouting shortest paths

Cited in

(4)

• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Changing induced subgraph isomorphisms under extended reconfiguration rules
• Parameterized shortest path reconfiguration
• Reachability of independent sets and vertex covers under extended reconfiguration rules

This page was built for publication: The shortest path reconfiguration problem based on relaxation of reconfiguration rules

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