From Pathwidth to Connected Pathwidth - Computer Science > Discrete MathematicsReportar como inadecuado

From Pathwidth to Connected Pathwidth - Computer Science > Discrete Mathematics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: It is proven that the connected pathwidth of any graph $G$ is at most$2\cdot\pwG+1$, where $\pwG$ is the pathwidth of $G$. The method isconstructive, i.e. it yields an efficient algorithm that for a given pathdecomposition of width $k$ computes a connected path decomposition of width atmost $2k+1$. The running time of the algorithm is $Odk^2$, where $d$ is thenumber of `bags- in the input path decomposition.The motivation for studying connected path decompositions comes from theconnection between the pathwidth and the search number of a graph. One of theadvantages of the above bound for connected pathwidth is an inequality$\csnG\leq 2\snG+3$, where $\csnG$ and $\snG$ are the connected searchnumber and the search number of $G$. Moreover, the algorithm presented in thiswork can be used to convert a given search strategy using $k$ searchers into amonotone connected one using $2k+3$ searchers and starting at an arbitraryhomebase.

Autor: Dariusz Dereniowski


Documentos relacionados