Back to Search
Start Over
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs.
- Source :
-
Algorithmica . Mar2019, Vol. 81 Issue 3, p1180-1204. 25p. - Publication Year :
- 2019
-
Abstract
- 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,nloglogn}) 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(nloglogn) time using O(n) bits. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 81
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 134970063
- Full Text :
- https://doi.org/10.1007/s00453-018-0464-z