THE COMPLEXITY OF SELECTION AND RANKING IN X + Y AND MATRICES WITH SORTED COLUMNS

被引：137

作者：

FREDERICKSON, GN

JOHNSON, DB

机构：

来源：

关键词：

D O I：

10.1016/0022-0000(82)90048-4

中图分类号：

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

学科分类号：

0812 ;

摘要：

引用

页码：197 / 208

页数：12

共 8 条

[1]

Bentley J. L., 1976, Information Processing Letters, V5, P82, DOI 10.1016/0020-0190(76)90071-5

[2]

BLUM M, 1972, J COMPUT SYST SCI, V7, P448

[3]

Fox B., 1966, MANAGE SCI, V13, P210

GALIL, Z ;

MEGIDDO, N .

[5] LOWER BOUNDS FOR SELECTION IN X + Y AND OTHER MULTI-SETS [J].

JOHNSON, DB ;

KASHDAN, SD .

[6] SELECTING KTH ELEMENT IN X+Y AND X1+X2+ ... +XM [J].

JOHNSON, DB ;

MIZOGUCHI, T .

[7]

Rabin M. O., 1972, Journal of Computer and System Sciences, V6, P639, DOI 10.1016/S0022-0000(72)80034-5

[8]

Shamos M. I., 1976, ALGORITHMS COMPLEXIT, P251