Algorithms and Complexity Group Wednesday, November 14, 2012: Reconfiguration of List L(2,1)-Labelings in a Graph

[wlr...@uwaterloo.ca]

A new Algorithms and Complexity Group event has been scheduled:

Reconfiguration of List L(2,1)-Labelings in a Graph

For an integer k >= 0, suppose that each vertex v of a graph G has a
set C(v) \\subseteq {0,1, ..., k} of labels, called a list of v. A list
L(2,1)-labeling of G is an assignment of a label in C(v) to each
vertex v of G such that every two adjacent vertices receive labels
which differ by at least 2 and every two vertices of distance two
receive labels which differ by at least 1. In this paper, we study the
problem of reconfiguring one list L(2,1)- labeling of a graph into
another list L(2,1)-labeling of the same graph by changing only one
label assignment at a time, while at all times maintaining a list
L(2,1)-labeling. First we show that this decision problem is
PSPACE-complete, even for bipartite planar graphs and k >= 6. In
contrast, we then show that the problem can be solved in linear time
for general graphs if k <= 4. We finally consider the problem
restricted to trees, and give a sufficient condition for which any two
list L(2,1)- labelings of a tree can be transformed into each other.

This appears in ISAAC 2012.


Date: Wednesday, November 14, 2012
Time: 13:30
Please look on WebCalendar to view this appointment.

http://www.cs.uwaterloo.ca/odyssey/event/1617