THE MAXIMUM FLOW PROBLEM IS LOG SPACE COMPLETE FOR P

被引：75

作者：

GOLDSCHLAGER, LM ^{[1
]}

SHAW, RA ^{[1
]}

STAPLES, J ^{[1
]}

机构：

[1] UNIV QUEENSLAND, DEPT COMP SCI, ST LUCIA, QLD 4067, AUSTRALIA

来源：

关键词：

D O I：

10.1016/0304-3975(82)90092-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：105 / 111

页数：7

共 13 条

[1] CHEN I, 1975, LECTURE NOTES COMPUT, V24, P306
[2] CHEN YK, 1973, 2ND P SAG COMP C PAR, P60
[3] OBSERVATION ON TIME-STORAGE TRADE OFF
COOK, SA
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) : 308 - 316
[4] LINEAR-PROGRAMMING IS LOG-SPACE HARD FOR P
DOBKIN, D
LIPTON, RJ
REISS, S
[J]. INFORMATION PROCESSING LETTERS, 1979, 8 (02) : 96 - 97
[5] Even S., 1979, GRAPH ALGORITHMS
[6] HIERARCHIES OF COMPLETE PROBLEMS
GALIL, Z
[J]. ACTA INFORMATICA, 1976, 6 (01) : 77 - 88
[7] Goldschlager L. M., 1977, SIGACT News, V9, P25, DOI 10.1145/1008354.1008356
[8] EPSILON-PRODUCTIONS IN CONTEXT-FREE GRAMMARS
GOLDSCHLAGER, LM
[J]. ACTA INFORMATICA, 1981, 16 (03) : 303 - 308
[9] Hopcroft J.E., 1979, INTRO AUTOMATA THEOR
[10] Jones N. D., 1976, Theoretical Computer Science, V3, P105, DOI 10.1016/0304-3975(76)90068-2