Parameterized shortest path reconfiguration

DOI10.4230/LIPICS.IPEC.2024.23MaRDI QIDQ7255461zbMATH OpenFDO

Authors Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, Amer E. Mouawad

Publication date 29 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2024.23

zbMATH Keywords

cluster deletion numbercombinatorial reconfigurationmodular widthparameterized complexityshortest path reconfigurationstructural parameterstreedepth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• Deciding first-order properties of nowhere dense graphs
• Feedback vertex set reconfiguration in planar graphs
• Flip distance between two triangulations of a point set is NP-complete
• Galactic token sliding
• Ground state connectivity of local Hamiltonians
• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Reconfiguration graphs of shortest paths
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of list edge-colorings in a graph
• Reconfiguring undirected paths
• Rerouting shortest paths in planar graphs
• The complexity of change
• The complexity of rerouting shortest paths
• The parameterized complexity of motion planning for snake-like robots
• The shortest path reconfiguration problem based on relaxation of reconfiguration rules

This page was built for publication: Parameterized shortest path reconfiguration

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