On the complexity of the shortest-path broadcast problem

详细信息    查看全文

• 作者：Pierluigi Crescenzi^a ; Pierre Fraigniaud^b ; ^{pierre.fraigniaud@liafa.univ-paris-diderot.fr" class="auth_mail" title="E-mail the corresponding author} ; Magnus Halldó ; rsson^c ; Hovhannes A. Harutyunyan^d ; Chiara Pierucci^a ; Andrea Pietracaprina^e ; Geppino Pucci^e
• 关键词：Broadcast time ; Shortest paths ; Communication networks ; Layered graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：30 January 2016
• 年：2016
• 卷：199
• 期：Complete
• 页码：101-109
• 全文大小：464 K

文摘

We study the shortest-path broadcast   problem in graphs and digraphs, where a message has to be transmitted from a source node class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15002267&_mathId=si12.gif&_user=111111111&_pii=S0166218X15002267&_rdoc=1&_issn=0166218X&md5=dd6362d53c96813c4dd5d75a0cb32411" title="Click to view the MathML source">sclass="mathContainer hidden">class="mathCode">$s$ to all the nodes along shortest paths, in the classical telephone model. For both graphs and digraphs, we show that the problem is equivalent to the broadcast problem in layered directed graphs. We then prove that this latter problem is NP-hard, and therefore that the shortest-path broadcast problem is NP-hard in graphs as well as in digraphs. Nevertheless, we prove that a simple polynomial-time algorithm, called class="sansserif">MDST-broadcast, based on min-degree spanning trees, approximates the optimal broadcast time within a multiplicative factor class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15002267&_mathId=si13.gif&_user=111111111&_pii=S0166218X15002267&_rdoc=1&_issn=0166218X&md5=e9a5b284891072e76c242998a9e56e20">class="imgLazyJSB inlineImage" height="21" width="8" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15002267-si13.gif">class="mathContainer hidden">class="mathCode">$\frac{3}{2}$ in 3-layer digraphs, and class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15002267&_mathId=si14.gif&_user=111111111&_pii=S0166218X15002267&_rdoc=1&_issn=0166218X&md5=00a25344a41127d5e9ab5d210feb8672">class="imgLazyJSB inlineImage" height="25" width="64" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15002267-si14.gif">class="mathContainer hidden">class="mathCode">$O\left(\frac{logn}{loglogn}\right)$ in arbitrary multi-layer digraphs. As a consequence, one can approximate the optimal shortest-path broadcast time in polynomial time within a multiplicative factor class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15002267&_mathId=si13.gif&_user=111111111&_pii=S0166218X15002267&_rdoc=1&_issn=0166218X&md5=e9a5b284891072e76c242998a9e56e20">class="imgLazyJSB inlineImage" height="21" width="8" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15002267-si13.gif">class="mathContainer hidden">class="mathCode">$\frac{3}{2}$ whenever the source has eccentricity at most 2, and within a multiplicative factor class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15002267&_mathId=si14.gif&_user=111111111&_pii=S0166218X15002267&_rdoc=1&_issn=0166218X&md5=00a25344a41127d5e9ab5d210feb8672">class="imgLazyJSB inlineImage" height="25" width="64" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15002267-si14.gif">class="mathContainer hidden">class="mathCode">$O\left(\frac{logn}{loglogn}\right)$ in the general case, for both graphs and digraphs. The analysis of class="sansserif">MDST-broadcast is tight, as we prove that this algorithm cannot approximate the optimal broadcast time within a factor smaller than class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15002267&_mathId=si17.gif&_user=111111111&_pii=S0166218X15002267&_rdoc=1&_issn=0166218X&md5=43fa982f3a2bcb6d6f6120961b4e6347">class="imgLazyJSB inlineImage" height="25" width="69" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X15002267-si17.gif">class="mathContainer hidden">class="mathCode">$\Omega \left(\frac{logn}{loglogn}\right)$.