|   | 
Author Kosowski, A.; Li, B.; Nisse, N.; Suchan, K.
Title k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth Type
Year 2015 Publication Algorithmica Abbreviated Journal Algorithmica
Volume 72 Issue 3 Pages (down) 758-777
Keywords Treewidth; Chordality; Compact routing; Cops and robber games
Abstract Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2-3), 235-239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89-92, 1985), 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 (chordless) cycle of length greater than k, ka parts per thousand yen3. 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 polynomial-time algorithm that, given a graph G and ka parts per thousand yen3, either returns an induced cycle larger than k in G, or computes a tree-decomposition of G, each 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 (Discrete Appl. Math. 79(1-3), 45-61, 1997. Moreover, any graph admitting such a tree-decomposition has small hyperbolicity). As an application, for any n-vertex graph admitting such a tree-decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klog Delta+logn) bits and achieving an additive stretch of O(klog Delta). As far as we know, this is the first routing scheme with O(klog Delta+logn)-routing tables and small additive stretch for k-chordal graphs.
Address [Kosowski, A.] INRIA, LaBRI, CEPAGE, Talence, France, Email: bi.li@inria.fr
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0178-4617 ISBN Medium
Area Expedition Conference
Notes WOS:000355939800004 Approved
Call Number UAI @ eduardo.moreno @ Serial 503
Permanent link to this record