Subexponential Parameterized Algorithm for Minimum Fill-in

Details Subexponential Parameterized Algorithm for Minimum Fill-in Subexponential Parameterized Algorithm for Minimum Fill-in

2011-04-12

arxiv.org/abs/1104.2230v1

Computer Science

Data Structures and Algorithms

23 pages, 1 figure

Scientific paper

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. Kaplan, Shamir, and Tarjan [FOCS 1994] have shown that the problem is solvable in time O(2^(O(k)) + k2 * nm) on graphs with n vertices and m edges and thus is fixed parameter tractable. Here, we give the first subexponential parameterized algorithm solving Minimum Fill-in in time O(2^(O(\sqrt{k} log k)) + k2 * nm). This substantially lower the complexity of the problem. Techniques developed for Minimum Fill-in can be used to obtain subexponential parameterized algorithms for several related problems including Minimum Chain Completion, Chordal Graph Sandwich, and Triangulating Colored Graph.

Affiliated with

Also associated with

No associations

Rating

Subexponential Parameterized Algorithm for Minimum Fill-in 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 Subexponential Parameterized Algorithm for Minimum Fill-in, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Subexponential Parameterized Algorithm for Minimum Fill-in will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-731073