Design and Engineering of External Memory Traversal Algorithms for General Graphs

DOI10.1007/978-3-642-02094-0_1zbMath1248.68364OpenAlexW1570377291MaRDI QIDQ3637309

Ulrich Meyer, Deepak Ajwani

Publication date: 9 July 2009

Published in: Algorithmics of Large and Complex Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02094-0_1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

Certifying induced subgraphs in large graphs

Uses Software

• LEDA
• TPIE
• STXXL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Random permutations on distributed, external and hierarchical memory
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• A functional approach to external graph algorithms
• A new approach to all-pairs shortest paths on real-weighted graphs
• Network analysis. Methodological foundations.
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Cache-Oblivious Algorithms
• An optimal minimum spanning tree algorithm
• Engineering a cache-oblivious sorting algorithm
• Cache-oblivious priority queue and graph algorithm applications
• A computational study of external-memory BFS algorithms
• Efficiency of a Good But Not Linear Set Union Algorithm
• A randomized linear-time algorithm to find minimum spanning trees
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Algorithms and Experiments for the Webgraph
• Algorithm Theory - SWAT 2004
• An improved equivalence algorithm
• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
• Automata, Languages and Programming
• Verification, Model Checking, and Abstract Interpretation
• Algorithms - ESA 2003
• Verification, Model Checking, and Abstract Interpretation
• Model Checking Software