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
Issue Date2015
Citation
Journal of Combinatorial Optimization (In press), 2015 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

 

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 (In press), 2015en_US
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.rightsCreative Commons: Attribution 3.0 Hong Kong License-
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.hkuros237839en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats