THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE

被引：21

作者：

JOHNSON, DS ^{[1
]}

机构：

[1] AT&T BELL LABS, MURRAY HILL, NJ 07974 USA

来源：

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1985年 / 6卷 / 01期

关键词：

D O I：

10.1016/0196-6774(85)90025-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：145 / 159

页数：15

共 50 条

[1] CONSTRAINED OPTIMUM COMMUNICATION TREES AND SENSITIVITY ANALYSIS [J].

AGARWAL, S ;

MITTAL, AK ;

SHARMA, P .

SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :315-328

[2] AN O(ABSOLUTE VALUE E) TIME ALGORITHM FOR COMPUTING THE RELIABILITY OF A CLASS OF DIRECTED NETWORKS [J].

AGRAWAL, A ;

SATYANARAYANA, A .

OPERATIONS RESEARCH, 1984, 32 (03) :493-515

[3]

Alon N., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P320, DOI 10.1109/SFCS.1984.715931

[4] CALCULATING BOUNDS ON REACHABILITY AND CONNECTEDNESS IN STOCHASTIC NETWORKS [J].

BALL, MO ;

PROVAN, JS .

NETWORKS, 1983, 13 (02) :253-278

[5] THE COMPLEXITY OF TESTING WHETHER A GRAPH IS A SUPERCONCENTRATOR [J].

BLUM, M ;

KARP, RM ;

VORNBERGER, O ;

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

INFORMATION PROCESSING LETTERS, 1981, 13 (4-5) :164-167

[6] THE BOUNDED PATH TREE PROBLEM [J].

CAMERINI, PM ;

GALBIATI, G .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (04) :474-484

[7] ON THE COMPLEXITY OF FINDING MULTI-CONSTRAINED SPANNING-TREES [J].

CAMERINI, PM ;

GALBIATI, G ;

MAFFIOLI, F .

DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) :39-50

[8] COMPLEXITY OF SPANNING TREE PROBLEMS .1. [J].

CAMERINI, PM ;

GALBIATI, G ;

MAFFIOLI, F .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1980, 5 (05) :346-352

[9]

CAMERINI PM, 1983, LCE831 DIP EL POL MI

[10]

CAMERINI PM, 1984, UNPUB 1984 P C THEOR

← 1 2 3 4 5 →