Constructing near spanning trees with few local inspections

详细信息    查看全文

• 作者：Reut Levi ; Guy Moshkovitz ; Dana Ron ; Ronitt Rubinfeld and Asaf Shapira
• 刊名：Random Structures & Algorithms
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：50
• 期：2
• 页码：183-200
• 全文大小：159K
• ISSN：1098-2418

文摘

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let m>Gm> be a connected bounded-degree graph. Given an edge m>em> in m>Gm> we would like to decide whether m>em> belongs to a connected subgraph math-equation-construct">mage="true" class="math-equation-image">mathml="true" class="math-equation-mathml" style="display:none"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow xmlns:w="http://www.wiley.com/namespaces/wiley" xmlns:wiley="http://www.wiley.com/namespaces/wiley/wiley" xmlns:cr="urn://wiley-online-library/content/render" xmlns="http://www.w3.org/1998/Math/MathML"><mi>Gmi><mo>′mo>mrow>mml:math> consisting of math-equation-construct">mage="true" class="math-equation-image">mathml="true" class="math-equation-mathml" style="display:none"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow xmlns:w="http://www.wiley.com/namespaces/wiley" xmlns:wiley="http://www.wiley.com/namespaces/wiley/wiley" xmlns:cr="urn://wiley-online-library/content/render" xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(mo><mn>1mn><mo>+mo><mo>ϵmo><mo stretchy="false">)mo><mi>nmi>mrow>mml:math> edges (for a prespecified constant math-equation-construct">mage="true" class="math-equation-image">mathml="true" class="math-equation-mathml" style="display:none"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow xmlns:w="http://www.wiley.com/namespaces/wiley" xmlns:wiley="http://www.wiley.com/namespaces/wiley/wiley" xmlns:cr="urn://wiley-online-library/content/render" xmlns="http://www.w3.org/1998/Math/MathML"><mo>ϵmo><mo>>mo><mn>0mn>mrow>mml:math>), where the decision for different edges should be consistent with the same subgraph math-equation-construct">mage="true" class="math-equation-image">mathml="true" class="math-equation-mathml" style="display:none"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow xmlns:w="http://www.wiley.com/namespaces/wiley" xmlns:wiley="http://www.wiley.com/namespaces/wiley/wiley" xmlns:cr="urn://wiley-online-library/content/render" xmlns="http://www.w3.org/1998/Math/MathML"><mi>Gmi><mo>′mo>mrow>mml:math>. Can this task be performed by inspecting only a m>constantm> number of edges in m>Gm>? Our main results are: