Minimum multicuts and Steiner forests for Okamura-Seymour graphs

Details Minimum multicuts and Steiner forests for Okamura-Seymour graphs Minimum multicuts and Steiner forests for Okamura-Seymour graphs

2011-02-27

arxiv.org/abs/1102.5478v1

Computer Science

Data Structures and Algorithms

6 pages, 1 figure

Scientific paper

We study the problem of finding minimum multicuts for an undirected planar graph, where all the terminal vertices are on the boundary of the outer face. This is known as an Okamura-Seymour instance. We show that for such an instance, the minimum multicut problem can be reduced to the minimum-cost Steiner forest problem on a suitably defined dual graph. The minimum-cost Steiner forest problem has a 2-approximation algorithm. Hence, the minimum multicut problem has a 2-approximation algorithm for an Okamura-Seymour instance.

Affiliated with

Also associated with

No associations

Rating

Minimum multicuts and Steiner forests for Okamura-Seymour graphs 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 Minimum multicuts and Steiner forests for Okamura-Seymour graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum multicuts and Steiner forests for Okamura-Seymour graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-53917