Graph searching and interval completion

DOI10.1137/S0895480199350477MaRDI QIDQ2706178zbMATH OpenFDO

Authors Fedor V. Fomin, Petr A. Golovach

Publication date 19 March 2001

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480199350477

zbMATH Keywords

cographgraph searchinginterval graph completionlinear layoutprofilesearch costvertex separation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

In the classical node-search version for a finite simple undirected graph, in a sequence of moves, at every move a searcher is placed at a vertex or is removed from a vertex. Initially all edges are contaminated (uncleared). A contaminated edge \(xy\) is cleared if on \(x\) and \(y\) searchers are placed. A cleared edge \(e\) is recontaminated if there is a path without searchers between \(e\) and a contaminated edge.NEWLINENEWLINENEWLINEThe classical search problem is to find a sequence of moves (a node-search program) such that the maximum number of searchers used at any move is minimal. In this paper, node-search programs with minimal sum of numbers of searchers are studied, where the sum is taken over all moves. This criterion is called search cost.NEWLINENEWLINENEWLINEThe paper shows monotonicity properties (with respect to recontamination) of search programs with smallest cost. The search cost of a graph \(G\) turns out to be the smallest edge number of an interval supergraph of \(G\) as well as the vertex separation sum and the profile of \(G\). Finally, the paper shows how to compute the search cost of the product of graphs and the search cost of a cograph. The corresponding search program can be determined in linear time.

Recommendations

• Interval graphs and searching
• Searching expenditure and interval graphs
• On minimum cost edge searching
• SOFSEM 2006: Theory and Practice of Computer Science
• Searching is not jumping.

Cited in

(25)

• Minimal interval completion through graph exploration
• On the profile of the corona of two graphs
• Interval propagation and search on directed acyclic graphs for numerical constraint solving
• Interval graphs and searching
• On the monotonicity of games generated by symmetric submodular functions.
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• Graph searching on some subclasses of chordal graphs
• On the domination search number
• On tradeoffs between width- and fill-like graph parameters
• Node-searching problem on block graphs
• Profile minimization on compositions of graphs
• On the interval completion of chordal graphs
• Computational graph completion
• scientific article; zbMATH DE number 1375600 (Why is no real title available?)
• On minimum cost edge searching
• Searching expenditure and interval graphs
• scientific article; zbMATH DE number 1472189 (Why is no real title available?)
• Network decontamination with temporal immunity by cellular automata
• The complexity of minimum-length path decompositions
• A cops and robber game and the meeting time of synchronous directed walks
• Time constrained graph searching
• An annotated bibliography on guaranteed graph searching
• Digraph searching, directed vertex separation and directed pathwidth
• Fixed-parameter complexity of minimum profile problems
• Maximum vertex occupation time and inert fugitive: Recontamination does help

This page was built for publication: Graph searching and interval completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706178)