Algorithm for solving the maximum leaf spanning tree problem on a bipartite graph with maximum degree three

Abstract

This thesis presents an algorithm for solving the maximum leaf spanning tree problem on a bipartite graph with maximum degree three. The maximum leaf spanning tree of a graph G is a spanning tree where the number of leaves is maximum among all possible spanning trees of G. The maximum leaf spanning tree problem is to find a maximum leaf spanning tree T of a given graph G. This problem is NP-Complete for regular graphs of degree three as well as for planar graphs of maximum degree four. A variation of this problem restricts to bipartite graphs and asks, for a fixed integer k, whether or not the graph contains a spanning tree with at least k leaves in one of the partite sets. This variation of the problem remains NP-Complete for planar bipartite graphs of maximum degree four. The maximum leaf spanning tree problem has applications in the area of communication networks. But this problem for bipartite graphs of maximum degree three has not been solved yet. In this thesis, an O(n2) time algorithm for solving the maximum leaf spanning tree problem on bipartite graphs of maximum degree three is presented.