### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 1-29 |

Number of pages | 29 |

Journal | Information sciences |

Volume | 81 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 1994 Nov |

### Fingerprint

### All Science Journal Classification (ASJC) codes

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

### Cite this

*Information sciences*,

*81*(1-2), 1-29. https://doi.org/10.1016/0020-0255(94)90086-8