### 摘要

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