Space-efficient basic graph algorithms

DOI10.4230/LIPICS.STACS.2015.288MaRDI QIDQ2955003zbMATH OpenOpenAlexFDO

Authors Amr Elmasry, Torben Hagerup, Frank Kammer

Publication date 24 January 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2015/4921/pdf/21.pdf/

zbMATH Keywords

depth-first searchgraph algorithmsregister input modelsingle-source shortest paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Space efficient linear time algorithms for BFS, DFS and applications
• Improved space efficient algorithms for BFS, DFS and applications
• Depth-First Search Using O(n) Bits
• scientific article; zbMATH DE number 1305462

Cited in

(35)

• Space-efficient Euler partition and bipartite edge coloring
• Space-efficient algorithms for longest increasing subsequence
• Approximation in (poly-) logarithmic space
• Space-efficient vertex separators for treewidth
• Depth-first search in directed planar graphs, revisited
• Reversibility of computations in graph-walking automata
• Frameworks for designing in-place graph algorithms
• Space efficient algorithms for breadth-depth search
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Space efficient linear time algorithms for BFS, DFS and applications
• Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
• Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
• Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS
• Improved space efficient algorithms for BFS, DFS and applications
• Space-efficient algorithms for longest increasing subsequence
• scientific article; zbMATH DE number 1305462 (Why is no real title available?)
• Efficient algorithms with asymmetric read and write costs
• Space-efficient biconnected components and recognition of outerplanar graphs
• Extra space during initialization of succinct data structures and dynamical initializable arrays
• A framework for in-place graph algorithms
• Optimal In-place Algorithms for Basic Graph Problems
• Simple 2f-Color Choice Dictionaries
• A constant-time colored choice dictionary with almost robust iteration
• Memory efficient algorithms for cactus graphs and block graphs
• Space-Efficient Euler Partition and Bipartite Edge Coloring
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• Space-efficient biconnected components and recognition of outerplanar graphs
• Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs
• Space-efficient graph coarsening with applications to succinct planar encodings
• Succinct data structure for chordal graphs with bounded vertex leafage
• Succinct planar encoding with minor operations
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism
• Lower bounds for graph-walking automata
• Trading uninitialized space for time
• A space-efficient algorithm for finding strongly connected components

This page was built for publication: Space-efficient basic graph algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955003)