Recently published journal publications--January 2011 (Expired)

The Department of Computer Science is pleased to announce the acceptance of a journal paper by a member of our department:

"Fast edge-searching and fast searching on graphs," by Boting Yang, Theoretical Computer Science.  Dr. Yang is a faculty member in our department.  Theoretical Computer Science is a leading venue for publishing theoretical research on Computer Science, DOI 10.1016/j.tcs.2010.12.065. For more information, see http://www.sciencedirect.com/science/journal/03043975 and look under articles in press, accepted January 1, 2011.

Abstract:

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 edge-searching problem in the edge search model, which is the problem of finding the minimum number of steps (called the fast edge-search time) to capture the fugitive. We establish relations between the fast edge-searching and the fast searching that is the problem of finding the minimum number of searchers to capture the fugitive in the fast search model. While the family of graphs whose fast search number is at most k is not minor-closed for any positive integer k2, we show that the family of graphs whose fast edge-search time is at most k is minor-closed. 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 edge-search numbers 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 NP-complete; and it remains NP-complete 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 NP-complete; and it remains NP-complete for planar graphs with maximum degree 4. We present a linear time approximation algorithm for the fast edge-search time that always delivers solutions of at most  (1 + (|V| - 1) / (|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.


Breaking News


Recent News


Do You Have News for the Department of Computer Science?

  • Please send a plain text version of your posting, which can include URL links, to deptsec@cs.uregina.ca
RSS
To Top of Page