## 摘要

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