SINGLE-STEP SEARCHING IN WEIGHTED BLOCK GRAPHS

In this paper, three types of problems for single step searching weigh ted graphs are investigated; the summation minimization (S-type, for s hort), 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 optimu m weight 2-independent set problem. Then we solve the S-type problem o n a block graph G in linear time by solving the optimum weight 2-indep endent set problem on G. To solve the B-type problem, the first phase computes the bottleneck cost and the second phase constructs the searc hing plan by applying the S-type algorithm using the bottleneck cost d erived in the first phase. Finally, an O(\E\log\V\) time algorithm for solving the H-type problem on weighted block graphs is proposed.