Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs
2019
We present space-efficient algorithms for computing cut vertices in a given graph with n vertices and m edges in linear time using \(O(n+\min \{m,n\log \log n\})\) bits. With the same time and using \(O(n+m)\) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in \(O(n\log \log n)\) time using O(n) bits.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
35
References
1
Citations
NaN
KQI