National Changhua University of Education Institutional Repository : Item 987654321/9977
English  |  正體中文  |  简体中文  |  Items with full text/Total items : 6507/11669
Visitors : 29719689      Online Users : 404
RC Version 3.2 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ir.ncue.edu.tw/ir/handle/987654321/9977

Title: Single step searching in weighted block graphs
Authors: Hsiao, Ju-Yuan;Tang, C. Y.;Chang, R. S.;Lee, R. C. T.
Contributors: 資訊工程系
Date: 1994-11
Issue Date: 2012-05-02T09:36:49Z
Publisher: Elsevier BV
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 time algorithm for solving the H-type problem on weighted block graphs is proposed.
Relation: Information Sciences, 81(1-2): 1-29
Appears in Collections:[Department and Graduate Institute of Computer Science and Information Engineering] Periodical Articles

Files in This Item:

File SizeFormat
2050400410002.pdf8KbAdobe PDF491View/Open


All items in NCUEIR are protected by copyright, with all rights reserved.

 


DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback