### 摘要

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(n^{2}) 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 十二月 20 → 2018 十二月 22 |

### 出版系列

名字 | Communications in Computer and Information Science |
---|---|

卷 | 1013 |

ISSN（列印） | 1865-0929 |

### Conference

Conference | 23rd International Computer Symposium, ICS 2018 |
---|---|

國家 | Taiwan |

城市 | Yunlin |

期間 | 18-12-20 → 18-12-22 |

### 指紋

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

### 引用此文

*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

}

*New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers.*Communications in Computer and Information Science, 卷 1013, Springer Verlag, 頁 524-531, 23rd International Computer Symposium, ICS 2018, Yunlin, Taiwan, 18-12-20. https://doi.org/10.1007/978-981-13-9190-3_58

**An Approximation Algorithm for Star p-Hub Routing Cost Problem.** / Hsieh, Sun-Yuan; Chen, Li Hsuan; Lu, Wei.

研究成果: Conference contribution

TY - GEN

T1 - An Approximation Algorithm for Star p-Hub Routing Cost Problem

AU - Hsieh, Sun-Yuan

AU - Chen, Li Hsuan

AU - Lu, Wei

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85069678421&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069678421&partnerID=8YFLogxK

U2 - 10.1007/978-981-13-9190-3_58

DO - 10.1007/978-981-13-9190-3_58

M3 - Conference contribution

AN - SCOPUS:85069678421

SN - 9789811391897

T3 - Communications in Computer and Information Science

SP - 524

EP - 531

BT - New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers

A2 - Chang, Chuan-Yu

A2 - Lin, Chien-Chou

A2 - Lin, Horng-Horng

PB - Springer Verlag

ER -