Exact Exponential Time Algorithms for Max Internal Spanning Tree

Henning Fernau, Serge Gaspers, Daniel Raible

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…