On computing the 2‐diameter ‐constrained K ‐reliability of networks. (13th August 2012)

• Record Type: Journal Article
• Authors: Canale, Eduardo; Cancela, Héctor; Robledo, Franco; Rubino, Gerardo; Sartor, Pablo
• Is Part Of: International transactions in operational research. Volume 20:Number 1(2013:Jan.)
• Page Start: 49
• Page End: 58
• Publication Date: 2012-08-13
• Subjects: Operations research -- Periodicals; 003
• DOI: 10.1111/j.1475-3995.2012.00864.x
• Languages: English
• ISSNs: 0969-6016

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>This article considers a communication network modeled by a graph <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3t7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:itor864:equation:itor864-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:mo><</mml:mo><mml:mi>V</mml:mi><mml:mo>, </mml:mo><mml:mi>E</mml:mi><mml:mo>></mml:mo></mml:mrow></mml:math> and a distinguished set of terminal nodes <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3sp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:itor864:equation:itor864-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>K</mml:mi><mml:mo>⊆</mml:mo><mml:mi>V</mml:mi></mml:mrow></mml:math>. We assume that the nodes never fail, but the edges fail randomly and independently with known probabilities. The classical <italic>K</italic> ‐reliability problem computes the probability that the subnetwork is composed only by the surviving edges in such a way that all terminals communicate with each other. The <italic>d</italic> ‐diameter ‐constrained <italic>K</italic> ‐reliability generalization also imposes the constraint that each pair of terminals must be the extremes of a surviving path of approximately <italic>d</italic> length. It allows modeling communication network situations in which limits exist on the acceptable delay times or on the amount of hops that packets can undergo. Both problems have been shown to be NP ‐hard, yet the complexity of certain subproblems remains undetermined. In particular, when <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3r4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:itor864:equation:itor864-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math>, it was an open question whether the instances with <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3qk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:itor864:equation:itor864-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>K</mml:mi><mml:mo>|</mml:mo><mml:mo>></mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> were solvable in polynomial time. In this paper, we prove that when <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3dm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:itor864:equation:itor864-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math> and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1f2hr3gq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:itor864:equation:itor864-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>K</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math> is a fixed parameter (i.e. not an input) the problem turns out to be polynomial in the number of nodes of the network (in fact linear). We also introduce an algorithm to compute these cases in such time and also provide two numerical examples.</p> </abstract>