publication . Preprint . Part of book or chapter of book . 2018

Compact I/O-Efficient Representation of Separable Graphs and Optimal Tree Layouts.

Tomáš Gavenčiak; Jakub Tětek;
Open Access English
  • Published: 16 Nov 2018
Abstract
Compact and I/O-efficient data representations play an important role in efficient algorithm design, as memory bandwidth and latency can present a significant performance bottleneck, slowing the computation by orders of magnitude. While this problem is very well explored in e.g. uniform numerical data processing, structural data applications (e.g. on huge graphs) require different algorithm-dependent approaches. Separable graph classes (i.e. graph classes with balanced separators of size $\mathcal{O}(n^c)$ with $c < 1$) include planar graphs, bounded genus graphs, and minor-free graphs. In this article we present two generalizations of the separator theorem, to ...
Subjects
free text keywords: Computer Science - Data Structures and Algorithms, Discrete mathematics, Computation, Algorithm design, Bounded function, Memory bandwidth, Separable space, Planar graph, symbols.namesake, symbols, Input/output, Combinatorics, Bottleneck, Computer science
Related Organizations
Download fromView all 2 versions
http://arxiv.org/pdf/1811.0674...
Part of book or chapter of book
Provider: UnpayWall
http://link.springer.com/conte...
Part of book or chapter of book
Provider: Crossref
35 references, page 1 of 3

[1] Agarwal, P.K., Arge, L., Murali, T., Varadarajan, K.R., Vitter, J.S.: I/Oe cient algorithms for contour-line extraction and planar graph blocking. In: SODA. pp. 117{126 (1998) [OpenAIRE]

[2] Aggarwal, A., Chandra, A.K., Snir, M.: Hierarchical memory with block transfer. In: Foundations of Computer Science. pp. 204{216. IEEE (1987)

[3] Aggarwal, A., Vitter, Je rey, S.: The input/output complexity of sorting and related problems. Commun. ACM 31(9), 1116{1127 (Sep 1988), http: //doi.acm.org/10.1145/48529.48535 [OpenAIRE]

[4] Blandford, D.K., Blelloch, G.E., Kash, I.A.: Compact representations of separable graphs. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 679{688. SIAM (2003)

[5] Blelloch, G.E., Farzan, A.: Succinct representations of separable graphs. In: Annual Symposium on Combinatorial Pattern Matching. pp. 138{150. Springer (2010) [OpenAIRE]

[6] Bollobas, B.: Modern graph theory. Springer (2010)

[7] Bringmann, K., Keusch, R., Lengler, J.: Sampling geometric inhomogeneous random graphs in linear time. In: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria. pp. 20:1{ 20:15 (2017) [OpenAIRE]

[8] Demaine, E.: Cache-oblivious algorithms and data structures. In: Lecture Notes from the EEF Summer School on Massive Data Sets (2002)

[9] Demaine, E.D., Iacono, J., Langerman, S.: Worst-case optimal tree layout in external memory. Algorithmica 72(2), 369{378 (Jun 2015)

[10] Dillabaugh, C., He, M., Maheshwari, A.: Succinct and I/O e cient data structures for traversal in trees. Algorithmica 63(1), 201{223 (Jun 2012), https://doi.org/10.1007/s00453-011-9528-z

[11] Dillabaugh, C., He, M., Maheshwari, A., Zeh, N.: I/O-e cient path traversal in succinct planar graphs. Algorithmica 77(3), 714{755 (2017)

[12] Farzan, A., Munro, J.I.: Succinct encoding of arbitrary graphs. Theoretical Computer Science 513, 38 { 52 (2013), http://www.sciencedirect.com/ science/article/pii/S0304397513007238

[13] Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science. pp. 285{. FOCS '99, IEEE Computer Society, Washington, DC, USA (1999), http://dl.acm.org/citation.cfm?id=795665. 796479

[14] Gamerman, D., Lopes, H.F.: Markov chain Monte Carlo: stochastic simulation for Bayesian inference. Chapman and Hall/CRC (2006)

[15] Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness (1979)

35 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Part of book or chapter of book . 2018

Compact I/O-Efficient Representation of Separable Graphs and Optimal Tree Layouts.

Tomáš Gavenčiak; Jakub Tětek;