Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time

Details Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time

2011-04-26

arxiv.org/abs/1104.4890v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present a deterministic O(n log log n) time algorithm for finding shortest
cycles and minimum cuts in planar graphs. The algorithm improves the previously
known fastest algorithm by Italiano et al. in STOC'11 by a factor of log n.
This speedup is obtained through the use of dense distance graphs combined with
a divide-and-conquer approach.

Affiliated with

Also associated with

No associations

Rating

Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Min-cuts and Shortest Cycles in Planar Graphs in O(n log log n) Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-296083