An O(n) Algorithm for ω-Path Partition of Edge-Weighted Forests
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    ω-path partition problem is the generalization of path partition problem. It comes of broadcasting communication in parallel computer system, computer network and distributed control system. This problem can be described by graph theory terminology as follows. Let G=(V,E) be an undirected simple graph with nonnegative edge-weights, and ω≥0 be a real. {P1, P2, …, Pm} is called to be an ω-path partition of G if P1, P2, …, Pm are m pairwise vertex-disjoint paths of G such that , and V(P)()(1GVPVmii==Ui)≤ω (for all i=1, 2, …, m, where W(Pi)= ). The ω-path partition number of G is the smallest cardinality of ω-path partition of G. The ω-path partition problem of G is to find a minimum ω-path partition and the ω-path partition number of G. It is evident that ω-path partition problem for any graph is NP-complete by the NP-completeness of Hamiltonian path. In this paper, some properties of ω-path partition have been investigated for paths, trees and forests with nonnegative edge-weights respectively. Linear time algorithms have been presented to solve ω-path partition problem for any path and tree with nonnegative edge-weights respectively. Local realization techniques and complexities of these two algorithms have been discussed in detail. Based above algorithms, an O(n) algorithm has been designed to solve ω-path partition problems for forests with nonnegative edge-weights. The algorithms presented in this paper are concise, and require less time and space.

    Reference
    Related
    Cited by
Get Citation

蔡延光,张新政,钱积新,孙优贤.边赋权森林ω-路划分的O(n)算法.软件学报,2003,14(5):897-903

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 28,2002
  • Revised:July 08,2002
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063