Space-efficient Basic Graph Algorithms

被引：22

作者：

Elmasry, Amr ^{[1
]}

Hagerup, Torben ^{[2
]}

Kammer, Frank ^{[2
]}

机构：

[1] Alexandria Univ, Dept Comp Engn & Syst, Alexandria 21544, Egypt

[2] Univ Augsburg, Inst Informat, D-86135 Augsburg, Germany

来源：

32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015) | 2015年 / 30卷

关键词：

graph algorithms; depth-first search; single-source shortest paths; register input model; POLYNOMIAL-TIME; SUBLINEAR SPACE; SHORTEST ROUTE; TRADE-OFFS; SELECTION; MEMORY; BOUNDS;

D O I：

10.4230/LIPIcs.STACS.2015.288

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of Theta(log log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.

引用

页码：288 / 301

页数：14

共 34 条

[1]

Aho A. V., 1983, DATA STRUCTURES ALGO

[2] Depth-First Search Using O(n) Bits [J].

Asano, Tetsuo ;

Izumi, Taisuke ;

Kiyomi, Masashi ;

Konagaya, Matsuo ;

Ono, Hirotaka ;

Otachi, Yota ;

Schweitzer, Pascal ;

Tarui, Jun ;

Uehara, Ryuhei .

ALGORITHMS AND COMPUTATION, ISAAC 2014, 2014, 8889 :553-564

[3] Reprint of: Memory-constrained algorithms for simple polygons [J].

Asano, Tetsuo ;

Buchin, Kevin ;

Buchin, Maike ;

Korman, Matias ;

Mulzer, Wolfgang ;

Rote, Guenter ;

Schulz, Andre .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (03) :469-479

[4]

Asano T, 2011, J COMPUT GEOM, V2, P46

[5]

Barba L., 2013, LIPICS, P281, DOI DOI 10.4230/LIPICS.STACS.2013.281

[6] Computing a visibility polygon using few variables [J].

Barba, Luis ;

Korman, Matias ;

Langerman, Stefan ;

Silveira, Rodrigo I. .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2014, 47 (09) :918-926

[7] A sublinear space, polynomial time algorithm for directed s-t connectivity [J].

Barnes, G ;

Buss, JF ;

Ruzzo, WL ;

Schieber, B .

SIAM JOURNAL ON COMPUTING, 1998, 27 (05) :1273-1282

[8] A GENERAL SEQUENTIAL TIME-SPACE TRADEOFF FOR FINDING UNIQUE ELEMENTS [J].

BEAME, P .

SIAM JOURNAL ON COMPUTING, 1991, 20 (02) :270-277

[9] Space-efficient planar convex hull algorithms [J].

Brönnimann, H ;

Iacono, J ;

Katajainen, J ;

Morin, P ;

Morrison, J ;

Toussaint, G .

THEORETICAL COMPUTER SCIENCE, 2004, 321 (01) :25-40

[10]

Chan T. M., 2014, PROC 25 ANN ACM SIAM, P995

← 1 2 3 4 →