PACKET ROUTING AND JOB-SHOP SCHEDULING IN O(CONGESTION PLUS DILATION) STEPS

被引：166

作者：

LEIGHTON, FT

MAGGS, BM

RAO, SB

机构：

[1] NEC RES INST,PRINCETON,NJ 08540

[2] CARNEGIE MELLON UNIV,SCH COMP SCI,PITTSBURGH,PA 15213

[3] MIT,DEPT MATH,CAMBRIDGE,MA 02139

[4] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

来源：

COMBINATORICA | 1994年 / 14卷 / 02期

关键词：

AMS subject classification code (1991): 68M20; 68M10; 68M07;

D O I：

10.1007/BF01215349

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, in O(c + d) steps, where c is the congestion of the paths in the network, and d is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.

引用

页码：167 / 186

页数：20

共 12 条

[1]

ALON N, 1991, 32ND ANN S F COMP SC, P586

[2]

BECK J, IN PRESS RANDOM STRU

[3]

LAWLER EL, 1989, BSR8909 CTR MATH COM

[4]

LEIGHTON FT, IN PRESS J ALGORITHM

[5]

LEIGHTON T, UNPUB FAST ALGORITHM

[6]

Ranade A. G., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P185, DOI 10.1109/SFCS.1987.32

[7]

SEVASTYANOV SV, 1986, KIBERNETIKA, V22, P74

[8]

SHMOYS DB, 1991, 2ND P ANN SIAM S DIS, P148

[9]

SPENCER J, 1987, 10 LECTURES PROBABIL

[10]

Thomson Leighton F., 1992, INTRO PARALLEL ALGOR

← 1 2 →