Beyond O*(2^n) in domination-type problems

Details Beyond O*(2^n) in domination-type problems Beyond O*(2^n) in domination-type problems

2009-09-22

arxiv.org/abs/0909.4021v1

Computer Science

Data Structures and Algorithms

Submitted to STACS 2010

Scientific paper

In this paper we provide algorithms faster than O*(2^n) for several NP-complete domination-type problems. More precisely, we provide: an algorithm for CAPACITATED DOMINATING SET that solves it in O(1.89^n), a branch-and-reduce algorithm solving LARGEST IRREDUNDANT SET in O(1.9657^n) time and a simple iterative-DFS algorithm for SMALLEST INCLUSION-MAXIMAL IRREDUNDANT SET that solves it in O(1.999956^n) time. We also provide an exponential approximation scheme for CAPACITATED DOMINATING SET. All algorithms require polynomial space. Despite the fact that the discussed problems are quite similar to the DOMINATING SET problem, we are not aware of any published algorithms solving these problems faster than the obvious O*(2^n) solution prior to this paper.

Affiliated with

Also associated with

No associations

Rating

Beyond O*(2^n) in domination-type problems 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 Beyond O*(2^n) in domination-type problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Beyond O*(2^n) in domination-type problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-301203