Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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})$.
Complete list of metadata
Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Saturday, October 10, 2009 - 1:32:59 PM
Last modification on : Thursday, August 4, 2022 - 4:52:39 PM


  • HAL Id : inria-00423448, version 1


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



Record views