Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
From MaRDI portal
Publication:2403234
DOI10.1016/j.jcss.2017.06.006zbMath1375.68089arXiv1606.08645OpenAlexW2963123976MaRDI QIDQ2403234
Srinivasa Rao Satti, Sankardeep Chakraborty, Venkatesh Raman
Publication date: 15 September 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.08645
depth-first searchbiconnectivityDFS\(st\)-numberingtopological sort2-edge connectivitylowpointspace-efficient graph algorithmssparse spanning biconnected subgraph
Analysis of algorithms (68W40) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Connectivity (05C40)
Related Items
Optimal In-place Algorithms for Basic Graph Problems ⋮ Succinct encodings for families of interval graphs ⋮ Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS ⋮ Frameworks for designing in-place graph algorithms ⋮ A Framework for In-place Graph Algorithms ⋮ Unnamed Item ⋮ Approximation in (Poly-) logarithmic space ⋮ Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster ⋮ Space efficient linear time algorithms for BFS, DFS and applications
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Path-based depth-first search for strong and biconnected components
- Reprint of: Memory-constrained algorithms for simple polygons
- Computing a visibility polygon using few variables
- Space-time trade-offs for stack-based algorithms
- Succinct representation of dynamic trees
- Selection from read-only memory and sorting with minimum data movement
- A simple optimal representation for balanced parentheses
- On the complexity of partitioning graphs into connected subgraphs
- Upper bounds for time-space trade-offs in sorting and selection
- The multi-tree approach to reliability in distributed networks
- Selection and sorting with limited storage
- st-ordering the vertices of biconnected graphs
- Partition conditions and vertex-connectivity of graphs
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Computing an st-numbering
- Independent trees in planar graphs
- A note on finding the bridges of a graph
- A simple test on 2-vertex- and 2-edge-connectivity
- Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
- Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
- On graph problems in a semi-streaming model
- Space Efficient Suffix Trees
- Succinct Representation of Balanced Parentheses and Static Trees
- Improved Space Efficient Algorithms for BFS, DFS and Applications
- Succinct Representations of Ordinal Trees
- 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
- Succinct ordinal trees with level-ancestor queries
- Space-efficient Basic Graph Algorithms
- New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
- Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs
- Succinct ordinal trees based on tree covering
- Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Three tree-paths
- Undirected connectivity in log-space
- Universal Succinct Representations of Trees?
- Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
- Space Lower Bounds for Maze Threadability on Restricted Machines
- Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- A homology theory for spanning tress of a graph
- 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
- Balanced parentheses strike back
- The Mondshein Sequence
- Embedding and canonizing graphs of bounded genus in logspace
- Computing with a full memory
- Computational Complexity
- Selection and Sorting in the “Restore” Model
- Finding Four Independent Trees
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
