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)

引用此

Hsieh, S-Y., Chen, L. H., & Lu, W. (2019). An Approximation Algorithm for Star p-Hub Routing Cost Problem. 於 C-Y. Chang, C-C. Lin, & H-H. Lin (編輯), New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers (頁 524-531). (Communications in Computer and Information Science; 卷 1013). Springer Verlag. https://doi.org/10.1007/978-981-13-9190-3_58