A Framework for In-place Graph Algorithms
From MaRDI portal
Publication:5009570
DOI10.4230/LIPICS.ESA.2018.13OpenAlexW2889523050MaRDI QIDQ5009570
Sankardeep Chakraborty, Venkatesh Raman, Srinivasa Rao Satti, Anish Mukherjee
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1711.09859
Related Items (7)
Optimal In-place Algorithms for Basic Graph Problems ⋮ Succinct encodings for families of interval graphs ⋮ Frameworks for designing in-place graph algorithms ⋮ Unnamed Item ⋮ Approximation in (Poly-) logarithmic space ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Simple 2^f-Color Choice Dictionaries
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reprint of: Memory-constrained algorithms for simple polygons
- Space-time trade-offs for stack-based algorithms
- An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
- Selection from read-only memory and sorting with minimum data movement
- Selection from read-only memory with limited workspace
- Multi-pass geometric algorithms
- Depth-first search is inherently sequential
- Parallelism and the maximal path problem
- Upper bounds for time-space trade-offs in sorting and selection
- A random NC algorithm for depth first search
- Selection and sorting with limited storage
- A time-space tradeoff for sorting on non-oblivious machines
- The space complexity of approximating the frequency moments
- 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
- On graph problems in a semi-streaming model
- Logspace optimization problems and their approximability properties
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
- Changing base without losing space
- Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
- $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient Basic Graph Algorithms
- New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
- Parallel Depth-First Search in General Directed Graphs
- Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Radix Sorting with No Extra Space
- Implicit dictionaries with O(1) modifications per update and fast search
- Undirected connectivity in log-space
- Symmetric Complementation
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Tight Lower Bounds for st-Connectivity on the NNJAG Model
- Canonizing Graphs of Bounded Tree Width in Logspace
- Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits
- Embedding and canonizing graphs of bounded genus in logspace
- Computing with a full memory
- Computational Complexity
- Towards in-place geometric algorithms and data structures
- Selection and Sorting in the “Restore” Model
- In-Place Suffix Sorting
This page was built for publication: A Framework for In-place Graph Algorithms
