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)


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
Issue number1-2
Publication statusPublished - 1993 Oct 15


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