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

DOI10.1016/j.tcs.2014.04.011zbMath1418.68170MaRDI 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 algorithm; PSPACE-completeness; \(L(2,1)\)-labeling; reachability on solution space

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

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