Biconnectivity, $st$-numbering and other applications of DFS using $O(n)$ bits (Q2403234): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2963123976
@@ Property / OpenAlex ID: W2963123976 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.08645
@@ Property / arXiv ID: 1606.08645 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Reprint of: Memory-constrained algorithms for simple polygons
+Normal rank
@@ Property / cites work @@
+Depth-First Search Using $$O(n)$$ Bits
@@ Property / cites work: Depth-First Search Using $$O(n)$$ Bits / rank @@
+Normal rank
@@ Property / cites work @@
+$\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
+Normal rank
@@ Property / cites work @@
+Improved Space Efficient Algorithms for BFS, DFS and Applications
+Normal rank
@@ Property / cites work @@
+Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
+Normal rank
@@ Property / cites work @@
+Space-time trade-offs for stack-based algorithms
@@ Property / cites work: Space-time trade-offs for stack-based algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Computing a visibility polygon using few variables
+Normal rank
@@ Property / cites work @@
+A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
+Normal rank
@@ Property / cites work @@
+A general Sequential Time-Space Tradeoff for Finding Unique Elements
+Normal rank
@@ Property / cites work @@
+Q4411363
@@ Property / cites work: Q4411363 / rank @@
+Normal rank
@@ Property / cites work @@
+Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time
+Normal rank
@@ Property / cites work @@
+Computing with a full memory
@@ Property / cites work: Computing with a full memory / rank @@
+Normal rank
@@ Property / cites work @@
+New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
+Normal rank
@@ Property / cites work @@
+Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits
+Normal rank
@@ Property / cites work @@
+Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications
+Normal rank
@@ Property / cites work @@
+Selection and Sorting in the “Restore” Model
@@ Property / cites work: Selection and Sorting in the “Restore” Model / rank @@
+Normal rank
@@ Property / cites work @@
+Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for <i>k</i>-Vertex Connectivity
+Normal rank
@@ Property / cites work @@
+Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
+Normal rank
@@ Property / cites work @@
+Space Lower Bounds for Maze Threadability on Restricted Machines
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Finding Four Independent Trees
@@ Property / cites work: Finding Four Independent Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem
+Normal rank
@@ Property / cites work @@
+On the complexity of partitioning graphs into connected subgraphs
+Normal rank
@@ Property / cites work @@
+st-ordering the vertices of biconnected graphs
@@ Property / cites work: st-ordering the vertices of biconnected graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Tight Lower Bounds for <i>st</i>-Connectivity on the NNJAG Model
+Normal rank
@@ Property / cites work @@
+Embedding and canonizing graphs of bounded genus in logspace
+Normal rank
@@ Property / cites work @@
+Canonizing Graphs of Bounded Tree Width in Logspace
+Normal rank
@@ Property / cites work @@
+Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs
+Normal rank
@@ Property / cites work @@
+Space-efficient Basic Graph Algorithms
@@ Property / cites work: Space-efficient Basic Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Computing an st-numbering
@@ Property / cites work: Computing an st-numbering / rank @@
+Normal rank
@@ Property / cites work @@
+Succinct representation of dynamic trees
@@ Property / cites work: Succinct representation of dynamic trees / rank @@
+Normal rank
@@ Property / cites work @@
+Universal Succinct Representations of Trees?
@@ Property / cites work: Universal Succinct Representations of Trees? / rank @@
+Normal rank
@@ Property / cites work @@
+On graph problems in a semi-streaming model
@@ Property / cites work: On graph problems in a semi-streaming model / rank @@
+Normal rank
@@ Property / cites work @@
+Upper bounds for time-space trade-offs in sorting and selection
+Normal rank
@@ Property / cites work @@
+Path-based depth-first search for strong and biconnected components
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+A simple optimal representation for balanced parentheses
+Normal rank
@@ Property / cites work @@
+Succinct ordinal trees with level-ancestor queries
+Normal rank
@@ Property / cites work @@
+Partition conditions and vertex-connectivity of graphs
+Normal rank
@@ Property / cites work @@
+Succinct ordinal trees based on tree covering
@@ Property / cites work: Succinct ordinal trees based on tree covering / rank @@
+Normal rank
@@ Property / cites work @@
+Independent trees in planar graphs
@@ Property / cites work: Independent trees in planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The multi-tree approach to reliability in distributed networks
+Normal rank
@@ Property / cites work @@
+Q4967204
@@ Property / cites work: Q4967204 / rank @@
+Normal rank
@@ Property / cites work @@
+A homology theory for spanning tress of a graph
@@ Property / cites work: A homology theory for spanning tress of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Balanced parentheses strike back
@@ Property / cites work: Balanced parentheses strike back / rank @@
+Normal rank
@@ Property / cites work @@
+Selection and sorting with limited storage
@@ Property / cites work: Selection and sorting with limited storage / rank @@
+Normal rank
@@ Property / cites work @@
+Selection from read-only memory and sorting with minimum data movement
+Normal rank
@@ Property / cites work @@
+Succinct Representation of Balanced Parentheses and Static Trees
+Normal rank
@@ Property / cites work @@
+Space Efficient Suffix Trees
@@ Property / cites work: Space Efficient Suffix Trees / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
+Normal rank
@@ Property / cites work @@
+Succinct Representations of Ordinal Trees
@@ Property / cites work: Succinct Representations of Ordinal Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q4719333
@@ Property / cites work: Q4719333 / rank @@
+Normal rank
@@ Property / cites work @@
+Undirected connectivity in log-space
@@ Property / cites work: Undirected connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+A simple test on 2-vertex- and 2-edge-connectivity
+Normal rank
@@ Property / cites work @@
+The Mondshein Sequence
@@ Property / cites work: The Mondshein Sequence / rank @@
+Normal rank
@@ Property / cites work @@
+Depth-First Search and Linear Graph Algorithms
@@ Property / cites work: Depth-First Search and Linear Graph Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+A note on finding the bridges of a graph
@@ Property / cites work: A note on finding the bridges of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q3719851
@@ Property / cites work: Q3719851 / rank @@
+Normal rank
@@ Property / cites work @@
+Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
+Normal rank
@@ Property / cites work @@
+Three tree-paths
@@ Property / cites work: Three tree-paths / rank @@
+Normal rank

Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits (Q2403234): Difference between revisions

Latest revision as of 09:30, 14 July 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)