File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10878-013-9697-6
- Scopus: eid_2-s2.0-84944276264
- WOS: WOS:000363033600024
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: The Minimum Number of Hubs in Networks
Title | The Minimum Number of Hubs in Networks |
---|---|
Authors | |
Keywords | Connectivity Menger’s theorem Vertex-disjoint paths |
Issue Date | 2015 |
Citation | Journal of Combinatorial Optimization, 2015, v. 30, p. 1196-1218 How to Cite? |
Abstract | In this paper, a hub refers to a non-terminal vertex of degree at least three. We study the minimum number of hubs needed in a network to guarantee certain flow demand constraints imposed between multiple pairs of sources and sinks. We prove that under the constraints, regardless of the size of the network, such minimum number is always upper bounded and we derive tight upper bounds for some special parameters. In particular, for two pairs of sources and sinks, we present a novel path-searching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds. Our results are of both theoretical and practical interest: in theory, they can be viewed as generalizations of the classical Menger’s theorem to a class of undirected graphs with multiple sources and sinks; in practice, our results, roughly speaking, suggest that for some given flow demand constraints, not “too many” hubs are needed in a network. |
Persistent Identifier | http://hdl.handle.net/10722/202987 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.370 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | XU, L | en_US |
dc.contributor.author | Han, G | en_US |
dc.date.accessioned | 2014-09-19T11:06:55Z | - |
dc.date.available | 2014-09-19T11:06:55Z | - |
dc.date.issued | 2015 | en_US |
dc.identifier.citation | Journal of Combinatorial Optimization, 2015, v. 30, p. 1196-1218 | en_US |
dc.identifier.issn | 1382-6905 | - |
dc.identifier.uri | http://hdl.handle.net/10722/202987 | - |
dc.description.abstract | In this paper, a hub refers to a non-terminal vertex of degree at least three. We study the minimum number of hubs needed in a network to guarantee certain flow demand constraints imposed between multiple pairs of sources and sinks. We prove that under the constraints, regardless of the size of the network, such minimum number is always upper bounded and we derive tight upper bounds for some special parameters. In particular, for two pairs of sources and sinks, we present a novel path-searching algorithm, the analysis of which is instrumental for the derivations of the tight upper bounds. Our results are of both theoretical and practical interest: in theory, they can be viewed as generalizations of the classical Menger’s theorem to a class of undirected graphs with multiple sources and sinks; in practice, our results, roughly speaking, suggest that for some given flow demand constraints, not “too many” hubs are needed in a network. | en_US |
dc.language | eng | en_US |
dc.relation.ispartof | Journal of Combinatorial Optimization | en_US |
dc.subject | Connectivity | - |
dc.subject | Menger’s theorem | - |
dc.subject | Vertex-disjoint paths | - |
dc.title | The Minimum Number of Hubs in Networks | en_US |
dc.type | Article | en_US |
dc.identifier.email | Han, G: ghan@hku.hk | en_US |
dc.identifier.authority | Han, G=rp00702 | en_US |
dc.description.nature | preprint | - |
dc.identifier.doi | 10.1007/s10878-013-9697-6 | - |
dc.identifier.scopus | eid_2-s2.0-84944276264 | - |
dc.identifier.hkuros | 237839 | en_US |
dc.identifier.volume | 30 | - |
dc.identifier.spage | 1196 | - |
dc.identifier.epage | 1218 | - |
dc.identifier.eissn | 1573-2886 | - |
dc.identifier.isi | WOS:000363033600024 | - |
dc.identifier.issnl | 1382-6905 | - |