Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering gr...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2009-04, Vol.157 (8), p.1913-1923
Main Authors: Yaşar, Öznur, Dyer, Danny, Pike, David A., Kondratieva, Margo
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Edge searching
Exact sciences and technology
Information retrieval. Graph
Mathematics
Monotonicity
Pathwidth
Problem solving, game playing
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2008.11.011