Directed planar reachability is in unambiguous log-space

被引：9

作者：

Bourke, Chris ^{[1
]}

Tewari, Raghunath ^{[1
]}

Vinodchandran, N. V. ^{[1
]}

机构：

[1] Univ Nebraska, Dept Comp Sci & Engn, Lincoln, NE 68588 USA

来源：

TWENTY-SECOND ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2007年

关键词：

D O I：

10.1109/CCC.2007.9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that the st-connectivity problem for directed planar graphs can be decided in unambiguous logarithmic space.

引用

页码：217 / +

页数：3

共 17 条

[1] The complexity of planarity testing [J].

Allender, E ;

Mahajan, M .

INFORMATION AND COMPUTATION, 2004, 189 (01) :117-134

[2] Isolation, matching, and counting uniform and nonuniform upper bounds [J].

Allender, E ;

Reinhardt, K ;

Zhou, SY .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 59 (02) :164-181

[3]

Allender E, 1998, THEOR COMPUT SYST, V31, P539, DOI 10.1007/s002240000102

[4]

ALLENDER E, 7 ANN INT S ALG COMP

[5]

ALLENDER E, 2005, P 25 ANN C FDN SOFTW

[6]

Allender E, 2006, ANN IEEE CONF COMPUT, P299

[7] A VERY HARD LOG-SPACE COUNTING CLASS [J].

ALVAREZ, C ;

JENNER, B .

THEORETICAL COMPUTER SCIENCE, 1993, 107 (01) :3-30

[8]

BUNTROCK G, 1991, LECT NOTES COMPUT SC, V529, P168

[9]

DAVID A, 1998, LECT NOTES COMPUTER, V1373, P74

[10]

DAVID A, 1989, J COMPUT SYST SCI, V38, P150

← 1 2 →