Loading...
Please wait, while we are loading the content...
Similar Documents
An $O(mn+n^{2}\log n) $ Time Cactus Construction Algorithm
| Content Provider | CiteSeerX |
|---|---|
| Author | Nagamochi, Hiroshi Nakamura, Shuji Ishii, Toshimasa |
| Abstract | It is known that all minimum cuts in an edge-weighted, undirected graph can be reP-raaeented by a cactus. In this paper, we show that such a cactus representation can be computed in $O(mn+n^{2}\log n) $ time and $O(m) $ space. This improves the previous best time bound of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing aminimum cut. 1 |
| File Format | |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
