{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T02:12:31Z","timestamp":1648519951048},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p> When analyzing a nonblocking switching network, the typical problem is to find a route for a new request through the network without disturbing existing routes. By solving this problem, we can derive how many hardware components of a certain type (Banyan planes in a multi-log network, for instance) are needed for the network to be nonblocking. This scenario appears in virtually all combinations of switching environments: strictly, widesense or rearrangeably nonblocking, unicast or multicast switching, and circuit, multirate, or photonic switching. <\/jats:p><jats:p> In this paper, we show that the K\u00f6nig\u2013Egevar\u00fd theorem is a very good tool which helps solve the above prototypical problem. The idea is to somehow \"represent\" the potential blocking connections as edges of a bipartite graph. The maximum number of blocking connections roughly corresponds to the size of a maximum matching in that bipartite graph. The size of any vertex cover, by the K\u00f6nig\u2013Egevar\u00fd theorem, is an upper bound on the maximum number of blocking connections. Thus, by specifying a small vertex cover, we can derive the sufficient number of hardware components for the network to be nonblocking. We illustrate the technique by analyzing crosstalk-free and non-crosstalk-free widesense nonblocking multicast multi-log networks. <\/jats:p><jats:p> Particularly, for the first time in the literature we derive conditions for the d-ary multi-log network to be crosstalk-free multicast widesense nonblocking under the window algorithm for any given window size. Several by-products follow from our approach and results. Firstly, our results allow for computing the best window size minimizing the fabric cost, showing that the multi-log network is a good candidate for crosstalk-free multicast switching architectures. Secondly, the analytical approach also gives a much simpler proof of the known case when the network is not required to be crosstalk-free. Thirdly, we show that several known results for the multi-log multicast networks under the so-called fanout constraints are simple corollaries of our results. <\/jats:p>","DOI":"10.1142\/s1793830909000117","type":"journal-article","created":{"date-parts":[[2009,4,8]],"date-time":"2009-04-08T04:55:25Z","timestamp":1239166525000},"page":"127-139","source":"Crossref","is-referenced-by-count":2,"title":["ANALYZING NONBLOCKING MULTILOG NETWORKS WITH THE K\u00d6NIG\u2013EGEVAR\u00dd THEOREM"],"prefix":"10.1142","volume":"01","author":[{"given":"HUNG Q.","family":"NGO","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, State University of New York at Buffalo, 201 Bell Hall, Amherst, New York, USA"}]},{"given":"THANH-NHAN","family":"NGUYEN","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, State University of New York at Buffalo, 201 Bell Hall, Amherst, New York, USA"}]},{"given":"DUC T.","family":"HA","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, State University of New York at Buffalo, 201 Bell Hall, Amherst, New York, USA"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1109\/50.400714"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2007.908541"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF00419002"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2003.818093"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1109\/26.664299"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/3640"},{"key":"rf7","author":"Jiang X.","journal-title":"IEEE T. Commun."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.820425"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2002.1010622"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/26.61445"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/26.87179"},{"key":"rf12","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","volume":"29","author":"Lov\u00e1sz L.","year":"1986"},{"key":"rf13","first-page":"1248","volume":"49","author":"Maier G.","journal-title":"IEEE T. Comm."},{"key":"rf14","volume-title":"Optical Communication Network","author":"Mukherjee B.","year":"1997"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442714"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0281-0_14"},{"key":"rf20","first-page":"69","volume":"8","author":"Qiao C.","journal-title":"J. High Speed Netw."},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1109\/26.103045"},{"key":"rf22","volume-title":"Multiwavelength Optical Networks: A Layered Approach","author":"Stern T. E.","year":"1999"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1109\/26.789678"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1109\/49.725200"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1109\/26.823564"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.113"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830909000117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:17:30Z","timestamp":1565129850000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830909000117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":23,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1142\/S1793830909000117"],"URL":"https:\/\/doi.org\/10.1142\/s1793830909000117","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]}}}