ON SOME VARIANTS OF THE BANDWIDTH MINIMIZATION PROBLEM

被引：75
作者：
LEUNG, JYT
VORNBERGER, O
WITTHOFF, JD
机构：
[1] UNIV PADERBORN, FACHBEREICH MATH INFORMAT, D-4790 PADERBORN, FED REP GER
[2] AT&T BELL LABS, NAPERVILLE, IL 60566 USA
来源：
SIAM JOURNAL ON COMPUTING | 1984年 / 13卷 / 03期
关键词：
COMPUTER SYSTEMS; DIGITAL; -; Multiprocessing; SCHEDULING;
D O I：
10.1137/0213040
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The authors consider the following variants of the bandwidth minimization problem: (1) the cycle-bandwidth problem which for a given graph G and positive integer k, asks if there is a circular layout such that every pair of adjacent vertexes have a distance at most k, (2) the separation problem which asks if there is a linear layout such that every pair of adjacent vertexes have a distance greater than k, and (3) the cycle-separation problem which asks if there is a circular layout such that every pair of adjacent vertexes have a distance greater than k. They show that the cycle-bandwidth problem is NP-complete for each fixed k greater than equivalent to 2, the separation and cycle-separation problems are both NP-complete for each fixed k greater than equivalent to 1, and the directed separation problem is NP-complete for arbitrary k. They give polynomial time algorithms for several special cases of the directed separation problem.
引用
收藏
页码：650 / 667
页数：18
相关论文
共 15 条
  • [1] Aho A. V., 1972, SIAM Journal on Computing, V1, P131, DOI 10.1137/0201008
  • [2] COFFMAN EG, 1972, ACTA INFORM, V1, P200, DOI DOI 10.1007/BF00288685
  • [3] Coffman Jr E. G., 1973, OPERATING SYSTEMS TH
  • [4] Gacril F., 1977, 11TH P C INF SCI SYS, P91
  • [5] Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1
  • [6] Garey M. R., 1977, SIAM Journal on Computing, V6, P416, DOI 10.1137/0206029
  • [7] Garey Michael R., 1979, COMPUTERS INTRACTABI
  • [8] COMPLEXITY RESULTS FOR BANDWIDTH MINIMIZATION
    GAREY, MR
    GRAHAM, RL
    JOHNSON, DS
    KNUTH, DE
    [J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 34 (03) : 477 - 495
  • [9] SCHEDULING UNIT-TIME TASKS WITH ARBITRARY RELEASE TIMES AND DEADLINES
    GAREY, MR
    JOHNSON, DS
    SIMONS, BB
    TARJAN, RE
    [J]. SIAM JOURNAL ON COMPUTING, 1981, 10 (02) : 256 - 269
  • [10] PARALLEL SEQUENCING AND ASSEMBLY LINE PROBLEMS
    HU, TC
    [J]. OPERATIONS RESEARCH, 1961, 9 (06) : 841 - 848
12