完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Yen, William Chung-Kung Jr | |
dc.contributor.author | Yang, Shung C-S Jr | |
dc.date.accessioned | 2011-02-21T23:27:11Z | |
dc.date.accessioned | 2020-05-18T03:22:24Z | - |
dc.date.available | 2011-02-21T23:27:11Z | |
dc.date.available | 2020-05-18T03:22:24Z | - |
dc.date.issued | 2011-02-21T23:27:11Z | |
dc.date.submitted | 2009-11-27 | |
dc.identifier.uri | http://dspace.lib.fcu.edu.tw/handle/2377/30026 | - |
dc.description.abstract | Let G(V, E) be an undirected and connected simple graph with n vertices. A positive weight 1w(v) is ociated to each vertex v and a positive length 2w(e) is ciated with each edge e. Given an integer p ≥ 1, the fundamental p-Center problem is to locate a p-vertex set Q of G for the establishment of facilities. Minimizing the maximum weighted distance for each vertex v in V – Q to its nearest facility site is the most important criteria. This paper focuses on the issue of finding connected p-centers on graphs, called the Connected p-Center problem (the CpC problem), which is a new practical variant from the p-Center problem. A p-center Q is connected if the subgraph induced by the vertices in Q is connected. Under the assumption that the clique path is given, this paper designs an O(n)-time algorithm for the CpC problem on interval graphs with 1w(v) = 1, for all tices v, and 2w(e) = 1, for all edges e. | |
dc.description.sponsorship | National Taipei University,Taipei | |
dc.format.extent | 6p. | |
dc.relation.ispartofseries | NCS 2009 | |
dc.subject | connected p-centers | |
dc.subject | NP-Hard | |
dc.subject | interval graphs | |
dc.subject | clique path | |
dc.subject.other | Workshop on Algorithms and Bioinformatics | |
dc.title | Finding Connected p-Centers on Interval Graphs | |
分類: | 2009年 NCS 全國計算機會議 |
文件中的檔案:
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
AB 1-2.pdf | 110.8 kB | Adobe PDF | 檢視/開啟 |
在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。