CONSTRUCTING A PERFECT MATCHING IS IN RANDOM NC

被引：117

作者：

KARP, RM

UPFAL, E

WIGDERSON, A

机构：

[1] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720

[2] IBM CORP,SAN JOSE RES LAB,SAN JOSE,CA 95193

[3] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305

来源：

COMBINATORICA | 1986年 / 6卷 / 01期

关键词：

D O I：

10.1007/BF02579407

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：35 / 48

页数：14

共 16 条

[1] FAST PROBABILISTIC ALGORITHMS FOR HAMILTONIAN CIRCUITS AND MATCHINGS [J].

ANGLUIN, D ;

VALIANT, LG .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1979, 18 (02) :155-193

[2] PARALLEL COMPUTATION FOR WELL-ENDOWED RINGS AND SPACE-BOUNDED PROBABILISTIC MACHINES [J].

BORODIN, A ;

COOK, S ;

PIPPENGER, N .

INFORMATION AND CONTROL, 1983, 58 (1-3) :113-136

[3]

BORODIN A, 1982, P STOC, V23, P65

[4]

Cook S. A., 1983, Communications of the ACM, V26, P400, DOI 10.1145/358141.358144

[5] SYSTEMS OF DISTINCT REPRESENTATIVES AND LINEAR ALGEBRA [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICAL SCIENCES, 1967, B 71 (04) :241-+

[6] THEORETICAL IMPROVEMENTS IN ALGORITHMIC EFFICIENCY FOR NETWORK FLOW PROBLEMS [J].

EDMONDS, J ;

KARP, RM .

JOURNAL OF THE ACM, 1972, 19 (02) :248-&

[7] THE MAXIMUM FLOW PROBLEM IS LOG SPACE COMPLETE FOR P [J].

GOLDSCHLAGER, LM ;

SHAW, RA ;

STAPLES, J .

THEORETICAL COMPUTER SCIENCE, 1982, 21 (01) :105-111

[8]

KARLOFF HJ, UNPUB LAS VEGAS RNC

[9]

KARP RM, 1985, STOC

[10]

KOZEN D, 1985, STOC

← 1 2 →