Monotony Properties of Connected Visible 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 : Search games are attractive for their correspondence with classical width parameters. For instance, the \emph{invisible} search number (a.k.a. \emph{node} search number) of a graph is equal to its pathwidth plus~1, and the \emph{visible} search number of a graph is equal to its treewidth plus~1. The \emph{connected} variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on \emph{monotone} search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an $n$-node graph is at most $O(\log n)$ times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is $\Omega(\log n)$. Second, we prove that, as opposed to the non-connected variant of visible graph searching, ``recontamination helps" for connected visible search. Precisely, we prove that, for any $k \geq 4$, there exists a graph with connected visible search number at most $k$, and monotone connected visible search number $>k$.
Type de document :
Communication dans un congrès
International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2006, Bergen, Norway. 2006
Liste complète des métadonnées

https://hal.inria.fr/inria-00423449
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:35:59
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04

Identifiants

  • HAL Id : inria-00423449, version 1

Collections

Citation

Pierre Fraigniaud, Nicolas Nisse. Monotony Properties of Connected Visible Graph Searching. International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 2006, Bergen, Norway. 2006. 〈inria-00423449〉

Partager

Métriques

Consultations de la notice

299