POLYNOMIAL-TIME ALGORITHMS FOR THE MIN CUT PROBLEM ON DEGREE RESTRICTED TREES

被引:36
作者
CHUNG, MJ
MAKEDON, F
SUDBOROUGH, IH
TURNER, J
机构
[1] IIT, DEPT COMP SCI, CHICAGO, IL 60616 USA
[2] NORTHWESTERN UNIV, DEPT ELECT ENGN & COMP SCI, EVANSTON, IL 60201 USA
[3] BELL TEL LABS INC, MURRAY HILL, NJ 07974 USA
关键词
D O I
10.1137/0214013
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
COMPUTER PROGRAMMING
引用
收藏
页码:158 / 177
页数:20
相关论文
共 44 条
[11]  
GAVRIL F, 11TH P C INF SCI SYS, P91
[12]  
GOLDBERG MK, 1976, MINIMAL PLACING TREE
[13]  
GURARI EM, UNPUB J ALGORITHMS
[14]  
IORDANSKII MA, 1974, SOV MATH DOKL, P1311
[15]  
LAPAUGH AS, 1983, RECONTAMINATION DOES
[16]  
LENGAUER T, 1981, ACTA INFORM, V16, P465, DOI 10.1007/BF00264496
[17]   THE SPACE COMPLEXITY OF PEBBLE GAMES ON TREES [J].
LENGAUER, T ;
TARJAN, RE .
INFORMATION PROCESSING LETTERS, 1980, 10 (4-5) :184-188
[18]   UPPER AND LOWER BOUNDS ON THE COMPLEXITY OF THE MIN-CUT LINEAR ARRANGEMENT PROBLEM ON TREES [J].
LENGAUER, T .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (01) :99-113
[19]   ASYMPTOTICALLY TIGHT BOUNDS ON TIME-SPACE TRADE-OFFS IN A PEBBLE GAME [J].
LENGAUER, T ;
TARJAN, RE .
JOURNAL OF THE ACM, 1982, 29 (04) :1087-1130
[20]   A DENSE GATE MATRIX LAYOUT METHOD FOR MOS VLSI [J].
LOPEZ, AD ;
LAW, HFS .
IEEE TRANSACTIONS ON ELECTRON DEVICES, 1980, 27 (08) :1671-1675