File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: The Minimum Number of Hubs in Networks

TitleThe Minimum Number of Hubs in Networks
Authors
KeywordsConnectivity
Menger’s theorem
Vertex-disjoint paths
Issue Date2015
Citation
Journal of Combinatorial Optimization, 2015, v. 30, p. 1196-1218 How to Cite?
AbstractIn 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 Identifierhttp://hdl.handle.net/10722/202987
ISSN
2019 Impact Factor: 0.843
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorXU, Len_US
dc.contributor.authorHan, Gen_US
dc.date.accessioned2014-09-19T11:06:55Z-
dc.date.available2014-09-19T11:06:55Z-
dc.date.issued2015en_US
dc.identifier.citationJournal of Combinatorial Optimization, 2015, v. 30, p. 1196-1218en_US
dc.identifier.issn1382-6905-
dc.identifier.urihttp://hdl.handle.net/10722/202987-
dc.description.abstractIn 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.languageengen_US
dc.relation.ispartofJournal of Combinatorial Optimizationen_US
dc.subjectConnectivity-
dc.subjectMenger’s theorem-
dc.subjectVertex-disjoint paths-
dc.titleThe Minimum Number of Hubs in Networksen_US
dc.typeArticleen_US
dc.identifier.emailHan, G: ghan@hku.hken_US
dc.identifier.authorityHan, G=rp00702en_US
dc.description.naturepreprint-
dc.identifier.doi10.1007/s10878-013-9697-6-
dc.identifier.scopuseid_2-s2.0-84944276264-
dc.identifier.hkuros237839en_US
dc.identifier.volume30-
dc.identifier.spage1196-
dc.identifier.epage1218-
dc.identifier.eissn1573-2886-
dc.identifier.isiWOS:000363033600024-
dc.identifier.issnl1382-6905-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats