Exact Exponential Time Algorithms for Max Internal Spanning Tree

Details Exact Exponential Time Algorithms for Max Internal Spanning Tree Exact Exponential Time Algorithms for Max Internal Spanning Tree

2008-11-12

arxiv.org/abs/0811.1875v3

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the NP-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form O*(c^n) (c <= 3). The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of O*(1.8669^n) when analyzed with respect to the number of vertices. We also show that its running time is 2.1364^k n^O(1) when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analyses for parameterized algorithms.

Affiliated with

Also associated with

No associations

Rating

Exact Exponential Time Algorithms for Max Internal Spanning Tree 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 Exact Exponential Time Algorithms for Max Internal Spanning Tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Exponential Time Algorithms for Max Internal Spanning Tree will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100966