Finding Shortest Paths Between Graph Colourings
- Submitting institution
-
University of Durham
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 96993
- Type
- D - Journal article
- DOI
-
10.1007/s00453-015-0009-7
- Title of journal
- Algorithmica
- Article number
- -
- First page
- 295
- Volume
- 75
- Issue
- 2
- ISSN
- 01784617
- Open access status
- Out of scope for open access requirements
- Month of publication
- -
- Year of publication
- 2015
- URL
-
https://doi.org/10.1007/s00453-015-0009-7
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
4
- Research group(s)
-
B - Algorithms and Complexity
- Citation count
- 15
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The first paper to consider combinatorial reconfiguration problems from the viewpoint of fixed parameter tractability, an approach followed by, for example, Hatanaka, Ito and Zhou, Complexity of Reconfiguration Problems for Constraint Satisfaction, Hatanaka, Ito and Zhou, Parameterized complexity of the list coloring reconfiguration problem with graph parameters, Ito, Kaminski and Ono, Fixed-Parameter Tractability of Token Jumping on Planar Graphs, Bonsma, Mouawad, Nishimura and Raman, The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration, Mouawad, Nishimura, Raman, Simjour, Suzuki, On the Parameterized Complexity of Reconfiguration Problems. One of the papers that established the area of combinatorial reconfigurations.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -