Single step searching in weighted block graphs

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

Research output: Contribution to journalArticle

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)1-29
Number of pages29
JournalInformation Sciences
Volume81
Issue number1-2
DOIs
Publication statusPublished - 1994 Nov

Fingerprint

Block graph
Costs
Polynomials
Independent Set
Graph Searching
Graph
Weighted Graph
Summation
Linear Time
NP-complete problem
Linearly
Polynomial

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

Hsiao, J. Y. ; Tang, C. Y. ; Chang, R. S. ; Lee, R. C.T. / Single step searching in weighted block graphs. In: Information Sciences. 1994 ; Vol. 81, No. 1-2. pp. 1-29.
@article{b709126b05f44b50906337d8b10173a9,
title = "Single step searching in weighted block graphs",
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.",
author = "Hsiao, {J. Y.} and Tang, {C. Y.} and Chang, {R. S.} and Lee, {R. C.T.}",
year = "1994",
month = "11",
doi = "10.1016/0020-0255(94)90086-8",
language = "English",
volume = "81",
pages = "1--29",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",
number = "1-2",

}

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

In: Information Sciences, Vol. 81, No. 1-2, 11.1994, p. 1-29.

Research output: Contribution to journalArticle

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 -