Photo from wikipedia
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\})$$O(n+min{m,nloglogn}) bits. With the same… Click to show full 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,n\log \log n\})$$O(n+min{m,nloglogn}) bits. With the same time and using $$O(n+m)$$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)$$O(nloglogn) time using O(n) bits.
Keywords:
biconnected components;
log;
outerplanar graphs;
space efficient
Journal Title: Algorithmica
Year Published: 2018
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!
Journal Title: Algorithmica
Year Published: 2018
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!