s'authentifier
version française rss feed

hal-00671861, version 4

k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth

Adrian Kosowski (, http://www.labri.fr/perso/kosowski) 1, Bi Li () 2, Nicolas Nisse () 2, Karol Suchan () 3

N° RR-7888 (2012)

Résumé : {\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.

  • Domaine : Informatique/Algorithme et structure de données
    Informatique/Mathématique discrète
  • Mots-clés : Treewidth – chordality – hyperbolicity – compact routing – cops and robber games
  • Référence interne : RR-7888
  • Versions disponibles :  v1 (19-02-2012) v2 (19-02-2012) v3 (20-02-2012) v4 (27-02-2012)
 
  • hal-00671861, version 4
  • oai:hal.archives-ouvertes.fr:hal-00671861
  • Contributeur : 
  • Soumis le : Vendredi 24 Février 2012, 16:16:21
  • Dernière modification le : Mercredi 29 Février 2012, 16:21:11
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...