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