Reconfiguration of list \(L(2,1)\)-labelings in a graph
From MaRDI portal
Publication:2250462
DOI10.1016/j.tcs.2014.04.011zbMath1418.68170MaRDI QIDQ2250462
Xiao Zhou, Hirotaka Ono, Takehiro Ito, Kazuto Kawamura
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
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, 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
