Binary linear programming models for robust broadcasting in communication networks

详细信息    查看全文

• 作者：Ronald G. McGarvey^a ; ^{mcgarveyr@missouri.edu" class="auth_mail" title="E-mail the corresponding author} ; Brian Q. Rieksts^b ; ^{brieksts@ida.org" class="auth_mail" title="E-mail the corresponding author} ; José ; A. Ventura^c ; ¹ ; ^{jav1@psu.edu" class="auth_mail" title="E-mail the corresponding author} ; Namsu Ahn^d ; ^{namsu.ahn@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Integer programming ; Communication networks ; Broadcasting ; Fault-tolerant networks
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 May 2016
• 年：2016
• 卷：204
• 期：Complete
• 页码：173-184
• 全文大小：823 K

文摘

Broadcasting is an information dissemination process in communication networks whereby a message, originated at any node of a network, is transmitted to all other nodes of the network. In class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcasting, each node having the message completes up to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$ transmissions to its neighbors over the communication lines in one time unit. In a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si32.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e5e47acaedd618e017380c5a3dd24f98" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-fault tolerant class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast network, the broadcasting process can be accomplished even if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si32.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e5e47acaedd618e017380c5a3dd24f98" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ communication lines fail. This paper presents innovative binary linear programming formulations to construct class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast graphs, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si32.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e5e47acaedd618e017380c5a3dd24f98" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-fault-tolerant class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast graphs, and their time-relaxed versions. The proposed mathematical models are used to generate eight previously unknown minimum class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast graphs, new upper bounds for eleven other instances of the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast problem, and over 30 minimum class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si32.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e5e47acaedd618e017380c5a3dd24f98" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-fault-tolerant class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast graphs. The paper also provides a construction method to produce an upper bound for an infinite family of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si32.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e5e47acaedd618e017380c5a3dd24f98" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-fault-tolerant class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005478&_mathId=si47.gif&_user=111111111&_pii=S0166218X15005478&_rdoc=1&_issn=0166218X&md5=e012c85549aad63f48beb31d78127a3a" title="Click to view the MathML source">cclass="mathContainer hidden">class="mathCode">$c$-broadcast graphs.