Shortest paths between shortest paths
type: Item
instance of: scholarly article
title: Shortest paths between shortest paths
zbMATH Open document ID: 1225.68136
author: Paul Medvedev
author: Martin Milanič
author: Marcin Kamiński
published in: Theoretical Computer Science
publication date: 2011-10-10T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 5955880
zbMATH Keywords: reconfiguration
zbMATH Keywords: shortest path
zbMATH Keywords: reconfigurability
zbMATH Keywords: NP-hard
zbMATH Keywords: diameter
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.05.021
OpenAlex ID: W2040122307
cites work: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
cites work: Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
cites work: Connectedness of the graph of vertex-colourings
cites work: Mixing 3-colourings in bipartite graphs
cites work: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
cites work: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
cites work: On the Complexity of Reconfiguration Problems
cites work: Reconfiguration of List Edge-Colorings in a Graph
cites work: Shortest Paths between Shortest Paths and Independent Sets
DOI: 10.1016/J.TCS.2011.05.021
description: scientific article; zbMATH DE number 5955880