THE COMPLEXITY OF RESTRICTED SPANNING TREE PROBLEMS

被引：115

作者：

PAPADIMITRIOU, CH

YANNAKAKIS, M

机构：

[1] MIT,CAMBRIDGE,MA 02139

[2] BELL TEL LABS INC,MURRAY HILL,NJ 07974

来源：

关键词：

D O I：

10.1145/322307.322309

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：285 / 309

页数：25

共 18 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2] PATHS TREES AND FLOWERS [J].

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (03) :449-&

[3]

Edmonds J., 1970, COMBINATORIAL STRUCT, P69

[4]

Edmonds J., 1971, MATH PROGRAM, V1, P127, DOI [10.1007/BF01584082, DOI 10.1007/BF01584082]

[5]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[6] 2-COMMODITY FLOW [J].

ITAI, A .

[7]

JOHNSON DS, 1976, COMMUNICATION FEB

[8]

Karp R.M., 1972, COMPLEXITY COMPUTER

[9]

Kruskal J.B., 1956, P AM MATH SOC, V7, P3, DOI [10.1090/S0002-9939-1956-0078686-7, DOI 10.1090/S0002-9939-1956-0078686-7, 10.2307/2033241]

[10] MATROID INTERSECTION ALGORITHMS [J].

LAWLER, EL .