REACHABILITY IS HARDER FOR DIRECTED THAN FOR UNDIRECTED FINITE GRAPHS

被引：68

作者：

AJTAI, M

FAGIN, R

机构：

来源：

关键词：

D O I：

10.2307/2274958

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：113 / 150

页数：38

共 37 条

[1]

AGGARWAL A, 1987, 19TH P ANN ACM S THE, P325

[2] SIGMA-11-FORMULAE ON FINITE STRUCTURES [J].

AJTAI, M .

[3]

Aleliunas R., 1979, 20th Annual Symposium of Foundations of Computer Science, P218, DOI 10.1109/SFCS.1979.34

[4]

ANDERSON R, 1987, COMMUNICATION MAY

[5]

BEERI C, 1987, 6TH P ACM S PRINC DA, P214

[6]

Berman P., 1983, 24th Annual Symposium on Foundations of Computer Science, P304, DOI 10.1109/SFCS.1983.31

[7]

BOLLOBAS B, 1982, RANDOM GRAPHS

[8]

BOPPANA RB, IN PRESS HDB THEORET

[9]

BORODIN A, 1988, 3RD STRUCT COMPL THE, P116

[10] STRUCTURE AND COMPLEXITY OF RELATIONAL QUERIES [J].

CHANDRA, A ;

HAREL, D .