Reconfiguration of list \(L(2,1)\)-labelings in a graph

DOI10.1016/j.tcs.2014.04.011zbMath1418.68170OpenAlexW1983081351MaRDI QIDQ2250462

Xiao Zhou, Kazuto Kawamura, Takehiro Ito, Hirotaka Ono

Publication date: 7 July 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.04.011

zbMATH Keywords

graph algorithmPSPACE-completeness\(L(2,1)\)-labelingreachability on solution space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

A dichotomy theorem for circular colouring reconfiguration ⋮ Complexity of the game domination problem ⋮ Linear-time algorithm for sliding tokens on trees ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Complexity of independent set reconfigurability problems
• Approximability of the subset sum reconfiguration problem
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• List version of \(L(d,s)\)-labelings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• A linear time algorithm for \(L(2,1)\)-labeling of trees
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Finding paths between 3-colorings
• Bipartite Edge Coloring in $O(\Delta m)$ Time
• Reconfiguration of List L(2,1)-Labelings in a Graph
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: Reconfiguration of list \(L(2,1)\)-labelings in a graph