On the Popular Spanning Tree Problem

Given an undirected connected graph G = (V, E) we consider the prob-lem of finding a spanning tree of G which preferred by the majority. We called it popular spanning trees problem (PST) and Condorcet spanning trees prob-lem (CST). In this thesis we mainly focus on when voter’s preference criteria is eccentricity on trees. On cycles, we show that finding a PST or verifying if a PST exists can be done in O(|V |2) time. On unit distance graph, we show that finding a PST or verifying if a PST exists can be done in O(|E|3) time, and for the special case where the center is unique, the shortest-path tree from it is a popular spanning tree. On general graphs, when absolute 1-center and Plural point coincide, the shortest-path tree from it is a popular spanning tree. Similarly, when absolute 1-center and Condorcet point coincide, the shortest-path tree from it is a Condorcet spanning tree.