Optimal In-place Algorithms for Basic Graph Problems
From MaRDI portal
Publication:5041185
DOI10.1007/978-3-030-48966-3_10OpenAlexW3029618096MaRDI QIDQ5041185
Sankardeep Chakraborty, Kunihiko Sadakane, Srinivasa Rao Satti
Publication date: 13 October 2022
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1907.09280
Related Items
Cites Work
- Unnamed Item
- 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 with limited workspace
- Multi-pass geometric algorithms
- Upper bounds for time-space trade-offs in sorting and selection
- Selection and sorting with limited storage
- Computing an st-numbering
- The space complexity of approximating the frequency moments
- A note on finding the bridges of a graph
- A simple test on 2-vertex- and 2-edge-connectivity
- Space efficient algorithms for breadth-depth search
- Linear-time in-place DFS and BFS on the word RAM
- 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, its applications, and variants of BFS
- On graph problems in a semi-streaming model
- Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers
- Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
- Depth-First Search Using $$O(n)$$ Bits
- Space-efficient Basic Graph Algorithms
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Radix Sorting with No Extra Space
- Implicit dictionaries with O(1) modifications per update and fast search
- A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
- Efficient Storage and Retrieval by Content and Address of Static Files
- Selection and Sorting in the “Restore” Model
- A Framework for In-place Graph Algorithms
- Computing with a full memory
- Towards in-place geometric algorithms and data structures
- In-Place Suffix Sorting
- Depth-First Search and Linear Graph Algorithms
