Connected Treewidth and Connected Graph Searching

Pierre Fraigniaud 1 Nicolas Nisse 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We give a constructive proof of the equality between \emph{treewidth} and \emph{connected treewidth}. More precisely, we describe an $O(nk^3)$-time algorithm that, given any $n$-node width-$k$ tree-decomposition of a connected graph $G$, returns a connected tree-decomposition of $G$ of width $\leq k$. The equality between treewidth and connected treewidth finds applications in \emph{graph searching} problems. First, using equality between treewidth and connected treewidth, we prove that the \emph{connected} search number $\cs(G)$ of a connected graph $G$ is at most $\log{n}+1$ times larger than its search number. Second, using our constructive proof of equality between treewidth and connected treewidth, we design an \\$O(\log n\sqrt{\log OPT})$-approximation algorithm for connected search, running in time $O(t(n)+nk^3\log^{3/2}k+m\log n)$ for $n$-node $m$-edge connected graphs of treewidth at most $k$, where $t(n)$ is the time-complexity of the fastest algorithm for approximating the treewidth, up to a factor $O(\sqrt{\log OPT})$.
Type de document :
Communication dans un congrès
Latin American Theoretical Informatics Symposium (LATIN), 2006, Valdivia, Chile. 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00423448
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:32:59
Dernière modification le : jeudi 11 janvier 2018 - 16:13:57

Identifiants

  • HAL Id : inria-00423448, version 1

Collections

Citation

Pierre Fraigniaud, Nicolas Nisse. Connected Treewidth and Connected Graph Searching. Latin American Theoretical Informatics Symposium (LATIN), 2006, Valdivia, Chile. 2006. 〈inria-00423448〉

Partager

Métriques

Consultations de la notice

231