The summation and bottleneck minimization for single-step searching on weighted graphs

Yuan Hsiao Ju Yuan Hsiao, Yi Tang Chuan Yi Tang, Shiung Chang Ruay Shiung Chang

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

In this paper, three types of problems for single-step searching weighted graphs are defined. They are the summation cost minimization, the bottleneck cost minimization, and a hybrid to minimize the maximum of the summation cost and the bottleneck cost. All three are shown to be NP-hard but polynomially solvable for trees. The bottleneck minimization is shown to be reducible to the summation minimization problem.

Original languageEnglish
Pages (from-to)1-28
Number of pages28
JournalInformation Sciences
Volume74
Issue number1-2
DOIs
Publication statusPublished - 1993 Oct 15

Fingerprint

Weighted Graph
Summation
Cost Minimization
Costs
Minimization Problem
NP-complete problem
Minimise
Graph
Cost minimization

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

Ju Yuan Hsiao, Yuan Hsiao ; Chuan Yi Tang, Yi Tang ; Ruay Shiung Chang, Shiung Chang. / The summation and bottleneck minimization for single-step searching on weighted graphs. In: Information Sciences. 1993 ; Vol. 74, No. 1-2. pp. 1-28.
@article{51275b2d5cb74c938b70cde8839d7d77,
title = "The summation and bottleneck minimization for single-step searching on weighted graphs",
abstract = "In this paper, three types of problems for single-step searching weighted graphs are defined. They are the summation cost minimization, the bottleneck cost minimization, and a hybrid to minimize the maximum of the summation cost and the bottleneck cost. All three are shown to be NP-hard but polynomially solvable for trees. The bottleneck minimization is shown to be reducible to the summation minimization problem.",
author = "{Ju Yuan Hsiao}, {Yuan Hsiao} and {Chuan Yi Tang}, {Yi Tang} and {Ruay Shiung Chang}, {Shiung Chang}",
year = "1993",
month = "10",
day = "15",
doi = "10.1016/0020-0255(93)90125-6",
language = "English",
volume = "74",
pages = "1--28",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier Inc.",
number = "1-2",

}

The summation and bottleneck minimization for single-step searching on weighted graphs. / Ju Yuan Hsiao, Yuan Hsiao; Chuan Yi Tang, Yi Tang; Ruay Shiung Chang, Shiung Chang.

In: Information Sciences, Vol. 74, No. 1-2, 15.10.1993, p. 1-28.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The summation and bottleneck minimization for single-step searching on weighted graphs

AU - Ju Yuan Hsiao, Yuan Hsiao

AU - Chuan Yi Tang, Yi Tang

AU - Ruay Shiung Chang, Shiung Chang

PY - 1993/10/15

Y1 - 1993/10/15

N2 - In this paper, three types of problems for single-step searching weighted graphs are defined. They are the summation cost minimization, the bottleneck cost minimization, and a hybrid to minimize the maximum of the summation cost and the bottleneck cost. All three are shown to be NP-hard but polynomially solvable for trees. The bottleneck minimization is shown to be reducible to the summation minimization problem.

AB - In this paper, three types of problems for single-step searching weighted graphs are defined. They are the summation cost minimization, the bottleneck cost minimization, and a hybrid to minimize the maximum of the summation cost and the bottleneck cost. All three are shown to be NP-hard but polynomially solvable for trees. The bottleneck minimization is shown to be reducible to the summation minimization problem.

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

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

U2 - 10.1016/0020-0255(93)90125-6

DO - 10.1016/0020-0255(93)90125-6

M3 - Article

AN - SCOPUS:0027677162

VL - 74

SP - 1

EP - 28

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

IS - 1-2

ER -