Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(10)
Approximate Algorithm
eulerian graph
Graph Search
Linear Time
Maximum Degree
Minimum Degree
Planar Graph
Search Model
Upper Bound
Lower Bound
Subscribe
Academic
Publications
Fast EdgeSearching and Related Problems
Fast EdgeSearching and Related Problems,10.1007/9783642174612_19,Boting Yang
Edit
Fast EdgeSearching and Related Problems
BibTex

RIS

RefWorks
Download
Boting Yang
Given a graph G = (V,E) in which a fugitive hides on vertices or along edges, graph searching problems are usually to find the minimum number of searchers required to capture the fugitive. In this paper, we consider the problem of finding the minimum number of steps to capture the fugitive. We introduce the fast edgesearching problem in the edge search model, which is the problem of finding the minimum number of steps (called the fast edgesearch time) to capture the fugitive. We establish relations between the fast edgesearch time and the fast search number. While the family of graphs whose fast search number is at most k is not minorclosed for any positive integer k ≥ 2, we show that the family of graphs whose fast edgesearch time is at most k is minorclosed. We establish relations between the fast (edge)searching and the node searching. These relations allow us to transform the problem of computing node search numbers to the problem of computing fast edgesearch time or fast search numbers. Using these relations, we prove that the problem of deciding, given a graph G and an integer k, whether the fast (edge)search number of G is less than or equal to k is NPcomplete; and it remains NPcomplete for Eulerian graphs. We also prove that the problem of determining whether the fast (edge)search number of G is a half of the number of odd vertices in G is NPcomplete; and it remains NPcomplete for planar graphs with
maximum degree
4. We present a
linear time
approximation algorithm for the fast edgesearch time that always delivers solutions of at most (1+\frac</font >V</font ></font >1</font >E</font >+1)(1+\frac{V1}{E+1}) times the optimal value. This algorithm also gives us a tight
upper bound
on the fast search number of the graph. We also show a
lower bound
on the fast search number using the
minimum degree
and the number of odd vertices.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 228242, 2010
DOI:
10.1007/9783642174612_19
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »