KLN+12b
Summary
Kosowski, Adrian, Li, Bi, Nisse, Nicolas and Suchan, Karol (2012) k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth. In 39th International Colloquium on Automata, Languages and Programming (ICALP, track C). jul. Springer, pages 610-622. ((URL)) (PDF)
Abstract
{\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of {$k$}-chordal graphs, i.e., graphs with no induced cycle of length greater than {$k$}, {$k\geq 3$}. We prove that {$k-1$} cops are always sufficient to capture a robber in {$k$}-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including {$k$}-chordal graphs. We present a quadratic algorithm that, given a graph {$G$} and {$k\geq 3$}, either returns an induced cycle larger than {$k$} in {$G$}, or computes a {\it tree-decomposition} of {$G$}, each {\it bag} of which contains a dominating path with at most {$k-1$} vertices. This allows us to prove that any {$k$}-chordal graph with maximum degree {$\Delta$} has treewidth at most {$(k-1)(\Delta-1)+2$}, improving the {$O(\Delta (\Delta-1)^{k-3})$} bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has hyperbolicity {$\leq\lfloor \frac{3}{2}k\rfloor$}. As an application, for any {$n$}-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size {$O(\log n)$} bits and achieving an additive stretch of {$O(k\log \Delta)$}. As far as we know, this is the first routing scheme with {$O(\log n)$}-routing tables and small additive stretch for {$k$}-chordal graphs. #KLN+12bBib
Bibtex entry
@INPROCEEDINGS { KLN+12b,
AUTHOR = { Kosowski, Adrian and Li, Bi and Nisse, Nicolas and Suchan, Karol },
TITLE = { k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth },
BOOKTITLE = { 39th International Colloquium on Automata, Languages and Programming (ICALP, track C) },
PUBLISHER = { Springer },
SERIES = { Lecture notes in computer science },
YEAR = { 2012 },
MONTH = { jul },
VOLUME = { 7392 },
PAGES = { 610-622 },
ABSTRACT = { {\it Cops and robber games} concern a team of cops that must capture a robber moving in a graph. We consider the class of {$k$}-chordal graphs, i.e., graphs with no induced cycle of length greater than {$k$}, {$k\geq 3$}. We prove that {$k-1$} cops are always sufficient to capture a robber in {$k$}-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including {$k$}-chordal graphs. We present a quadratic algorithm that, given a graph {$G$} and {$k\geq 3$}, either returns an induced cycle larger than {$k$} in {$G$}, or computes a {\it tree-decomposition} of {$G$}, each {\it bag} of which contains a dominating path with at most {$k-1$} vertices. This allows us to prove that any {$k$}-chordal graph with maximum degree {$\Delta$} has treewidth at most {$(k-1)(\Delta-1)+2$}, improving the {$O(\Delta (\Delta-1)^{k-3})$} bound of Bodlaender and Thilikos (1997). Moreover, any graph admitting such a tree-decomposition has hyperbolicity {$\leq\lfloor \frac{3}{2}k\rfloor$}. As an application, for any {$n$}-node graph admitting such a tree-decomposition, we propose a {\it compact routing scheme} using routing tables, addresses and headers of size {$O(\log n)$} bits and achieving an additive stretch of {$O(k\log \Delta)$}. As far as we know, this is the first routing scheme with {$O(\log n)$}-routing tables and small additive stretch for {$k$}-chordal graphs. },
URL = { http://hal.inria.fr/hal-00671861 },
PDF = { http://hal.archives-ouvertes.fr/docs/00/67/18/97/PDF/RR-7888.pdf },
}