### 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

}

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

**Single step searching in weighted block graphs.** / Hsiao, J. Y.; Tang, C. Y.; Chang, R. S.; Lee, R. C.T.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Single step searching in weighted block graphs

AU - Hsiao, J. Y.

AU - Tang, C. Y.

AU - Chang, R. S.

AU - Lee, R. C.T.

PY - 1994/11

Y1 - 1994/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028544273&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028544273&partnerID=8YFLogxK

U2 - 10.1016/0020-0255(94)90086-8

DO - 10.1016/0020-0255(94)90086-8

M3 - Article

AN - SCOPUS:0028544273

VL - 81

SP - 1

EP - 29

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - 1-2

ER -