On Multiway Cut parameterized above lower bounds

Details On Multiway Cut parameterized above lower bounds On Multiway Cut parameterized above lower bounds

2011-07-08

arxiv.org/abs/1107.1585v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper we consider two above lower bound parameterizations of the Node Multiway Cut problem - above the maximum separating cut and above a natural LP-relaxation - and prove them to be fixed-parameter tractable. Our results imply O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost 2-SAT as well as an O*(2^k) algorithm for Node Multiway Cut with a standard parameterization by the solution size, improving previous bounds for these problems.

Affiliated with

Also associated with

No associations

Rating

On Multiway Cut parameterized above lower bounds 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 On Multiway Cut parameterized above lower bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Multiway Cut parameterized above lower bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-221970