頁籤選單縮合
題 名 | An Optimal Algorithm for Edge Searching an Interval Graph |
---|---|
作 者 | 張瑞雄; | 書刊名 | Journal of Information Science and Engineering |
卷 期 | 9:3 1993.09[民82.09] |
頁 次 | 頁421-430 |
分類號 | 310.15 |
關鍵詞 | Graph theory; Interval graph; Edge search number; Node search number; Algorithms; |
語 文 | 英文(English) |
英文摘要 | Consider the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edge of a graph, G, in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number, s(G), of searchers that will suffice to guarantee capture of the fugitive? This is called the edge searching problem. This problem is slightly different from the node searching problem, where the clearing of an edge takes place once both its endpoints simultaneously carry a searcher. Both searching problems have been proved to be NP-hard and it has been shown that the node searcher number of an interval graph is equivalent to the size of its maximum clique. In this paper, we present an optimal algorithm to edge-search an interval graph. Conditions are also shown when the edge search number and the node search number are equal and when they differ by 1 for interval graphs. |
本系統中英文摘要資訊取自各篇刊載內容。