### Abstract

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.

Original language | English |
---|---|

Title of host publication | New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers |

Editors | Chuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin |

Publisher | Springer Verlag |

Pages | 524-531 |

Number of pages | 8 |

ISBN (Print) | 9789811391897 |

DOIs | |

Publication status | Published - 2019 Jan 1 |

Event | 23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan Duration: 2018 Dec 20 → 2018 Dec 22 |

### Publication series

Name | Communications in Computer and Information Science |
---|---|

Volume | 1013 |

ISSN (Print) | 1865-0929 |

### Conference

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

Country | Taiwan |

City | Yunlin |

Period | 18-12-20 → 18-12-22 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

### Cite this

*New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers*(pp. 524-531). (Communications in Computer and Information Science; Vol. 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, vol. 1013, Springer Verlag, pp. 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.

Research output: Chapter in Book/Report/Conference proceeding › 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 -