Reconfiguring shortest paths in graphs
type: Item
instance of: scholarly article
title: Reconfiguring shortest paths in graphs
author: Kshitij Gajjar
author: Agastya Vibhuti Jha
author: Manish Kumar
author: Abhiruk Lahiri
published in: Algorithmica
publication date: 2024-10-24T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7931155
zbMATH Keywords: reconfiguration
zbMATH Keywords: shortest path
zbMATH Keywords: PSPACE-complete
zbMATH Keywords: circle graph
zbMATH Keywords: Boolean hypercube
zbMATH Keywords: bridged graph
zbMATH Keywords: line graph
zbMATH Keywords: hardness of approximation
MaRDI profile type: Publication
cites work: Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
cites work: Algorithms for Solving Rubik’s Cubes
cites work: Solving the Rubik's Cube Optimally is NP-complete
cites work: Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
cites work: Reconfiguring dominating sets in some well-covered and other classes of graphs
cites work: Q4607889
cites work: Reconfiguration in bounded bandwidth and tree-depth
cites work: Reconfiguration on sparse graphs
cites work: Introduction to reconfiguration
cites work: On the parameterized complexity of reconfiguration problems
cites work: Shortest Paths between Shortest Paths and Independent Sets
cites work: Reducing Multiple Object Motion Planning to Graph Searching
cites work: Movement Problems for 2-Dimensional Linkages
cites work: The complexity of rerouting shortest paths
cites work: Rerouting shortest paths in planar graphs
cites work: Reconfiguration graphs of shortest paths
cites work: Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
cites work: Algorithms for a maximum clique and a maximum independent set of a circle graph
cites work: Container stowage planning: a methodology for generating computerised solutions
cites work: Stowage planning for container ships to reduce the number of shifts
cites work: Container ship stowage problem complexity and connection to the coloring of circle graphs
cites work: On the complexity of container stowage planning problems
cites work: Distance-Preserving Subgraphs of Interval Graphs
cites work: Applying the corridor method to a blocks relocation problem
cites work: A mathematical formulation and complexity considerations for the blocks relocation problem
cites work: The train marshalling problem
cites work: Minimizing delays in a shunting yard
cites work: Solving the train marshalling problem by inclusion-exclusion
cites work: Permutation Graphs and Transitive Graphs
cites work: Q3328583
cites work: Graph Classes: A Survey
cites work: Packet routing in fixed-connection networks: A survey
cites work: Deflection routing in hypercube networks
cites work: Q3574266
cites work: SHARC
cites work: Reach for A*: Efficient Point-to-Point Shortest Path Algorithms
cites work: Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
cites work: Conditions for invariance of set diameters under d-convexification in a graph
cites work: On local convexity in graphs
cites work: A Helly theorem in weakly modular space
cites work: Q3983321
cites work: An Efficient Test for Circular-Arc Graphs
cites work: A simpler linear-time recognition of circular-arc graphs
cites work: Shortest paths between shortest paths
DOI: 10.1007/S00453-024-01263-Y
description: scientific article; zbMATH DE number 7931155