首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:A Message-Optimal Distributed Graph Algorithm: Partial Precedence Constrained Scheduling
  • 本地全文:下载
  • 作者:P. Chaudhuri, H. Thompson
  • 期刊名称:Journal of Universal Computer Science
  • 印刷版ISSN:0948-6968
  • 出版年度:2004
  • 卷号:10
  • 期号:2
  • 页码:106-119
  • DOI:10.3217/jucs-010-02
  • 出版社:Graz University of Technology and Know-Center
  • 摘要:This paper presents a distributed algorithm for the partial precedence constrained scheduling problem. In the classical precedence constrained scheduling problem all the dependent tasks must be scheduled before the task itself can be scheduled. The partial precedence constrained scheduling problem is a generalized version of the original precedence constrained problem in the sense that the number of dependent tasks to be scheduled before the task itself can be scheduled is considered a variable. Using a directed graph to model the partial precedence constrained scheduling problem in which n nodes represent the tasks and e edges represent the precedence constraints, it is shown that the distributed algorithm requires O(e) messages and O(n) units of time and is optimal in communication complexity to within a constant factor
  • 关键词:directed graph, distributed algorithm, precedence constraints, scheduling, task
国家哲学社会科学文献中心版权所有