Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50082
Title: | 大眾化生成樹問題 On the Popular Spanning Tree Problem |
Authors: | Wei-Cheng Lin 林蔚城 |
Advisor: | 趙坤茂(Kun-Mao Chao) |
Keyword: | 生成樹,投票理論, spanning trees,voting theory, |
Publication Year : | 2016 |
Degree: | 碩士 |
Abstract: | 生成樹問題向來是離散數學與演算法領域中經典的最佳化問題。常應用於現代網路模型及協定之建構,探討如何在最小成本情況下使得各節點之間具連通的功能。而本論文所提出的生成樹,希望從相關傳統問題尋常切入的兩個方向(最小化最大以及最小化總和)外,發展出另一套與投票理論相遇之模型。我們將問題的定義回歸到每個節點自身的需求上。這些需求可能是從自己走到樹中最遠點的距離,也可能是經過樹中每個點的距離總和,或是在樹中與自己相鄰的點數等。我們根據一些初步觀察到的性質,提出在某些情況下有效率的算法,探討如何尋找一棵儘可能滿足大眾偏好的生成樹。 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50082 |
DOI: | 10.6342/NTU201601989 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-105-1.pdf Restricted Access | 894.16 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.