Single step searching in weighted block graphs

J. Y. Hsiao, C. Y. Tang, R. S. Chang, R. C.T. Lee

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)

摘要

In this paper, three types of problems for single step searching weighted graphs are investigated; the summation minimization (S-type, for short), bottleneck minimization (B-type, for short), and hybrid (H-type, for short) weighted single step graph searching problems. All three types are shown to be NP-hard but polynomial solvable for block graphs. The S-type problem is proved to be linearly equivalent to the optimum weight 2-independent set problem. Then we solve the S-type problem on a block graph G in linear time by solving the optimum weight 2-independent set problem on G. To solve the B-type problem, the first phase computes the bottleneck cost and the second phase constructs the searching plan by applying the S-type algorithm using the bottleneck cost derived in the first phase. Finally, an O(|E|log|V) time algorithm for solving the H-type problem on weighted block graphs is proposed.

原文English
頁(從 - 到)1-29
頁數29
期刊Information sciences
81
發行號1-2
DOIs
出版狀態Published - 1994 十一月

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

指紋 深入研究「Single step searching in weighted block graphs」主題。共同形成了獨特的指紋。

引用此