An Approximation Algorithm for Star p-Hub Routing Cost Problem

Sun-Yuan Hsieh, Li Hsuan Chen, Wei Lu

研究成果: Conference contribution

摘要

Given a metric graph G = (V,E,w), a center c ε V, and an integer p, we discuss the Star p-Hub Routing Cost Problem in this paper. We want obtain a depth-2 tree which has a root and root is adjacent to p vertices called hubs. We call that this tree is a star p-hub tree and let the sum of distance in tree between all pairs of vertices be minimum. We prove the Star p-Hub Routing Cost Problem is NP-hard by reducing the Exact Cover by 3-Sets Problem to it. The Exact Cover by 3-Sets Problem is a variation of set cover problem and known NP-hard problem. After proving the Star p-Hub Routing Cost Problem is NP-hard, we present a 4-approximation algorithm running in polynomial time O(n2) for the Star p-Hub Routing Cost Problem.

原文English
主出版物標題New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
編輯Chuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
發行者Springer Verlag
頁面524-531
頁數8
ISBN(列印)9789811391897
DOIs
出版狀態Published - 2019 一月 1
事件23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan
持續時間: 2018 十二月 202018 十二月 22

出版系列

名字Communications in Computer and Information Science
1013
ISSN(列印)1865-0929

Conference

Conference23rd International Computer Symposium, ICS 2018
國家Taiwan
城市Yunlin
期間18-12-2018-12-22

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

指紋 深入研究「An Approximation Algorithm for Star p-Hub Routing Cost Problem」主題。共同形成了獨特的指紋。

引用此