連通p-中心點問題之研究; The Connected p-Center Problem

uTaipei > College of Science > Department of Computer Science > Research Project > Item 987654321/16018

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16018

Title:	連通p-中心點問題之研究;The Connected p-Center Problem
Authors:	陳彥宏
Contributors:	臺北市立大學資訊科學系
Keywords:	組合最佳化;圖論;瓶頸問題;min-max問題;p-中心點問題;連通p-中心點問題;設備配置;社交網路;負載平衡;NP-hard;可近似度集合;近似演算法;正確演算法;啟發式算法;作業研究;網路路由
Date:	2014-11-01
Issue Date:	2017-07-31 13:51:32 (UTC+8)
Abstract:	本計畫是探討一個組合最佳化的問題，命名為連通p-中心點問題(Connected p-Center Problem)。此問題為p-中心點問題(p-Center Problem)的變形問題。p-中心點問題是圖論上很典型的一個瓶頸問題 (bottleneck problem，或稱為min-max problem)，主要是應用在設備配置(facility location)及社交網路 (social network)上，而最小連通p-中心點問題擴展設備配置的應用到具有備份(backup)及負載平衡(load balancing)機制的設備配置上。給定一個無向圖G=(V,E,l)及一個非負數的長度函數l在邊上和一個整數 p，\|V\|>p>0，p-中心點是在圖G中找一個p個節點(稱為中心節點)的集合C，\|C\|=p，V\C內的每個節點可透過最短路徑連通到其最近的中心節點。而一個圖的離心率則定義為每個節點到其最近的中心節點中最遠的那一段距離的值。p-中心點問題(p-Center problem)定義為找到一個p-中心點，使得離心率要最小。一個連通p-中心點是在圖G中找一個p個節點的集合P，\|P\|=p，V\P內的每個節點可透過最短路徑連通到其最近的中心節點而且這p個中心節點的induced subgraph必須是連通。連通p-中心點問題 (Connected p-Center (CpC) Problem)定義為找到一個一個連通p-中心點，使得離心率要最小。CpC問題已被證明為NP-hard。本計劃我們將探討此問題的可近似度集合或設計近似演算法(approximation algorithms)、正確演算法(exact algorithms)或啟發式演算法(heuristic algorithms)來解決這個問題並模擬在作業研究(operations research)及網路路由(network routing)的資料上。我們也有興趣討論權重版的連通p-中心點問題的可近似度集合及設計其近似演算法。
Relation:	研究期間：民10208~10307，國科會計畫編號：NSC102-2221-E845-003
Appears in Collections:	[Department of Computer Science] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	2325	View/Open

Loading...