Full complexity analysis of the diameter‐constrained reliability. (27th March 2015)

• Record Type: Journal Article
• Authors: Canale, Eduardo; Cancela, Héctor; Robledo, Franco; Romero, Pablo; Sartor, Pablo
• Is Part Of: International transactions in operational research. Volume 22:Number 5(2015:Sep.)
• Page Start: 811
• Page End: 821
• Publication Date: 2015-03-27
• Subjects: Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12159
• Languages: English
• ISSNs: 0969-6016

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2kz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-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></alternatives></inline-formula> be a simple graph with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2n2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>V</mml:mi><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></alternatives></inline-formula> nodes and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2mh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>E</mml:mi><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:math></alternatives></inline-formula> links, a subset <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2q5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0004" 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></alternatives></inline-formula> of "terminals, " a vector <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2pm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mrow><mml:mo>(</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:mo>...</mml:mo><mml:mo>, </mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mi>m</mml:mi></mml:msub><mml:mo>)</mml:mo></mml:mrow><mml:mo>∈</mml:mo><mml:msup><mml:mrow><mml:mo>[</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo>]</mml:mo></mml:mrow><mml:mi>m</mml:mi></mml:msup></mml:mrow></mml:math></alternatives></inline-formula>, and a positive integer <italic>d</italic>, called "diameter." We assume that nodes are perfect but links fail stochastically and independently, with probabilities <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2s8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>q</mml:mi><mml:mi>i</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mi>p</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:mrow></mml:math></alternatives></inline-formula>. The "diameter‐constrained reliability" (DCR) is the probability that the terminals of the resulting subgraph remain connected by paths composed of <italic>d</italic> links, or less. This number is denoted by <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2rq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msubsup><mml:mi>R</mml:mi><mml:mrow><mml:mi>K</mml:mi><mml:mo>, </mml:mo><mml:mi>G</mml:mi></mml:mrow><mml:mi>d</mml:mi></mml:msubsup><mml:mrow><mml:mo>(</mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives></inline-formula>. The general DCR computation belongs to the class of <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2hv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">N</mml:mi><mml:mi mathvariant="script">P</mml:mi></mml:mrow></mml:math></alternatives></inline-formula>‐hard problems, since it subsumes the problem of computing the probability that a random graph is connected. The contributions of this paper are twofold. First, a full analysis of the computational complexity of DCR subproblems is presented in terms of the number of terminal nodes <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2c0rk2g9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:09696016:media:itor12159:itor12159-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mo>|</mml:mo><mml:mi>K</mml:mi><mml:mo>|</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> and the diameter <italic>d</italic>. Second, we extend the class of graphs that accept efficient DCR computation. In this class, we include graphs with bounded co‐rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant to robust network design.</p> </abstract>