A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds

Details A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds

2009-06-07

arxiv.org/abs/0906.1356v3

Computer Science

Data Structures and Algorithms

Scientific paper

We introduce a new approach for establishing fixed-parameter tractability of problems parameterized above tight lower bounds. To illustrate the approach we consider three problems of this type of unknown complexity that were introduced by Mahajan, Raman and Sikdar (J. Comput. Syst. Sci. 75, 2009). We show that a generalization of one of the problems and non-trivial special cases of the other two are fixed-parameter tractable.

Affiliated with

Also associated with

No associations

Rating

A Probabilistic Approach to Problems Parameterized Above or Below Tight 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 A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-370149