<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426--441]: given a “contaminated†graph G (e.g., a network containing a hostile intruder), the search number View the MathML source of the graph G is the minimum number of searchers needed to “clear†the graph (or to capture the intruder). A search strategy is connected if, at every step of the strategy, the set of cleared edges induces a connected subgraph. The connected search number View the MathML source of a graph G is the minimum k such that there exists a connected search strategy for the graph G using at most k searchers. This paper is concerned with the ratio between the connected search number and the search number. We prove that, for any chordal graph G of treewidth View the MathML source, View the MathML source. More precisely, we propose a polynomial-time algorithm that, given any chordal graph G, computes a connected search strategy for G using at most View the MathML source searchers. Our main tool is the notion of connected tree-decomposition. We show that, for any connected graph G of chordality k, there exists a connected search strategy using at most View the MathML source searchers where T is an optimal tree-decomposition of G.
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Treewidth, Chordal graphs, Applied Mathematics, Discrete Mathematics and Combinatorics, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph Searching
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Treewidth, Chordal graphs, Applied Mathematics, Discrete Mathematics and Combinatorics, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Graph Searching
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |