| Summary: | For a <i>vertex and edge weighted</i> (VEW) graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>G</mi></semantics></math></inline-formula> with a vertex weight function <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>f</mi><mi>G</mi></msub></mrow></semantics></math></inline-formula> let <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>W</mi><mrow><mi>α</mi><mo>,</mo><mi>β</mi></mrow></msub><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><munder><mo>∑</mo><mrow><mrow><mo>{</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow><mo>}</mo></mrow><mo>⊆</mo><mi>V</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></munder><mrow><mo>[</mo><mrow><mi>α</mi><msub><mi>f</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>×</mo><msub><mi>f</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo>+</mo><mi>β</mi><mo stretchy="false">(</mo><msub><mi>f</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>u</mi><mo>)</mo></mrow><mo>+</mo><msub><mi>f</mi><mi>G</mi></msub><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow><mo stretchy="false">)</mo></mrow><mo>]</mo></mrow><msub><mi>d</mi><mi>G</mi></msub><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow><mo>)</mo></mrow></mrow></semantics></math></inline-formula> where, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>α</mi><mo>,</mo><mi>β</mi><mo>∈</mo><mo>ℝ</mo></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>d</mi><mi>G</mi></msub><mrow><mo>(</mo><mrow><mi>u</mi><mo>,</mo><mi>v</mi></mrow><mo>)</mo></mrow></mrow></semantics></math></inline-formula> denotes the distance, the minimum sum of edge weights across all the paths connecting <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>u</mi><mo>,</mo><mi>v</mi><mo>∈</mo><mi>V</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>. Assume <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>T</mi></semantics></math></inline-formula> is a VEW tree, and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mo>∈</mo><mo> </mo><mi>E</mi><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> fails. If we reconnect the two components of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>T</mi><mo>−</mo><mi>e</mi></mrow></semantics></math></inline-formula> with new edge <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ϵ</mi><mo>≠</mo><mi>e</mi></mrow></semantics></math></inline-formula> such that, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>W</mi><mrow><mi>α</mi><mo>,</mo><mi>β</mi></mrow></msub><mrow><mo>(</mo><mrow><msub><mi>T</mi><mrow><mi>ϵ</mi><mo>\</mo><mi>e</mi></mrow></msub><mo>=</mo><mi>T</mi><mo>−</mo><mi>e</mi><mo>+</mo><mi>ϵ</mi></mrow><mo>)</mo></mrow></mrow></semantics></math></inline-formula> is minimum, then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>ϵ</mi></semantics></math></inline-formula> is called a <i>best switch</i> (BS) of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>e</mi></semantics></math></inline-formula> w.r.t. <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>W</mi><mrow><mi>α</mi><mo>,</mo><mi>β</mi></mrow></msub></mrow></semantics></math></inline-formula>. We define three notions: convexity, discrete derivative, and discrete integral for the VEW graphs. As an application of the notions, we solve some BS problems for positively VEW trees. For example, assume <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>T</mi></mrow></semantics></math></inline-formula> is an <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>n</mi></semantics></math></inline-formula>-vertex VEW tree. Then, for the inputs <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>e</mi><mo>∈</mo><mo> </mo><mi>E</mi><mrow><mo>(</mo><mi>T</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mo>,</mo><mi>α</mi><mo>,</mo><mi>β</mi><mo> </mo><mo>∈</mo><msup><mo>ℝ</mo><mo>+</mo></msup></mrow></semantics></math></inline-formula>, we return <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>ϵ</mi></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>T</mi><mrow><mi>ϵ</mi><mo>\</mo><mi>e</mi></mrow></msub></mrow></semantics></math></inline-formula>, and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>W</mi><mrow><mi>α</mi><mo>,</mo><mi>β</mi></mrow></msub><mrow><mo>(</mo><mrow><msub><mi>T</mi><mrow><mi>ϵ</mi><mo>\</mo><mi>e</mi></mrow></msub></mrow><mo>)</mo></mrow></mrow></semantics></math></inline-formula> with the worst average time of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mi>n</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula> and the best time of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>ϵ</mi></semantics></math></inline-formula> is a BS of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>e</mi></semantics></math></inline-formula> w.r.t. <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>W</mi><mrow><mi>α</mi><mo>,</mo><mi>β</mi></mrow></msub></mrow></semantics></math></inline-formula> and the weight of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>ϵ</mi></semantics></math></inline-formula> is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>w</mi></semantics></math></inline-formula>.
|
|---|