TY - JOUR
T1 - The Alcuin number of a graph and its connections to the vertex cover number
AU - Csorba, P.
AU - Hurkens, C.A.J.
AU - Woeginger, G.J.
PY - 2012
Y1 - 2012
N2 - We consider a planning problem that generalizes Alcuin's river crossing problem to scenarios with arbitrary conflict graphs. This generalization leads to the so-called Alcuin number of the underlying conflict graph. We derive a variety of combinatorial, structural, algorithmical, and complexity theoretical results around the Alcuin number. Our technical main result is an NP-certificate for the Alcuin number. It turns out that the Alcuin number of a graph is closely related to the size of a minimum vertex cover in the graph, and we unravel several surprising connections between these two graph parameters. We provide hardness results and a fixed parameter tractability result for computing the Alcuin number. Furthermore we demonstrate that the Alcuin number of chordal graphs, bipartite graphs, and planar graphs is substantially easier to analyze than the Alcuin number of general graphs.
Key words: transportation problem, scheduling and planning, graph theory, vertex cover
This paper originally appeared in SIAM Journal on Discrete Mathematics, Volume 24, Number 3, 2010, pages 757–769.
AB - We consider a planning problem that generalizes Alcuin's river crossing problem to scenarios with arbitrary conflict graphs. This generalization leads to the so-called Alcuin number of the underlying conflict graph. We derive a variety of combinatorial, structural, algorithmical, and complexity theoretical results around the Alcuin number. Our technical main result is an NP-certificate for the Alcuin number. It turns out that the Alcuin number of a graph is closely related to the size of a minimum vertex cover in the graph, and we unravel several surprising connections between these two graph parameters. We provide hardness results and a fixed parameter tractability result for computing the Alcuin number. Furthermore we demonstrate that the Alcuin number of chordal graphs, bipartite graphs, and planar graphs is substantially easier to analyze than the Alcuin number of general graphs.
Key words: transportation problem, scheduling and planning, graph theory, vertex cover
This paper originally appeared in SIAM Journal on Discrete Mathematics, Volume 24, Number 3, 2010, pages 757–769.
U2 - 10.1137/110848840
DO - 10.1137/110848840
M3 - Article
VL - 54
SP - 141
EP - 154
JO - SIAM Review
JF - SIAM Review
SN - 0036-1445
IS - 1
ER -