Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits

DOI10.4230/LIPIcs.ISAAC.2016.22zbMath1398.05193OpenAlexW2463761753MaRDI QIDQ4636504

Sankardeep Chakraborty, Venkatesh Raman, Srinivasa Rao Satti

Publication date: 19 April 2018

Full work available at URL: https://arxiv.org/abs/1606.08645

zbMATH Keywords

biconnectivitytree coverread-only memorychain decompositionspace efficient algorithms\(st\)-number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Space-efficient Euler partition and bipartite edge coloring ⋮ 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 ⋮ Space-efficient biconnected components and recognition of outerplanar graphs ⋮ A Framework for In-place Graph Algorithms ⋮ Space efficient linear time algorithms for BFS, DFS and applications

This page was built for publication: Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits