Narrow sieves for parameterized paths and packings

Details Narrow sieves for parameterized paths and packings Narrow sieves for parameterized paths and packings

2010-07-07

arxiv.org/abs/1007.1161v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present randomized algorithms for some well-studied, hard combinatorial problems: the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space; the constant bases of the exponentials are significantly smaller than in previous works. For example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with $d$ colors in time within a polynomial factor of O(2^{(d-1)n/2}). Our techniques build upon and generalize some recently published ideas by I. Koutis (ICALP 2009), R. Williams (IPL 2009), and A. Bj\"orklund (STACS 2010, FOCS 2010).

Affiliated with

Also associated with

No associations

Rating

Narrow sieves for parameterized paths and packings 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 Narrow sieves for parameterized paths and packings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Narrow sieves for parameterized paths and packings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345618