Spanning tree

Summary

In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself). Applications Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem. In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree. The Internet and many other telecommunications

Official source

https://en.wikipedia.org/wiki/Spanning_tree

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (11)

Related publications

Related people

Related units

Related concepts (24)

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is,

Related concepts

Related courses (11)

Related courses

Related lectures (32)

Related lectures

A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms

Felix Gaertner

Self-stabilizing systems can automatically recover from arbitrary state perturbations in finite time. They are therefore well-suited for dynamic, failure prone environments. Spanning-tree construction in distributed systems is a fundamental task which forms the basis for many other network algorithms (like token circulation or routing).This paper surveys self-stabilizing algorithms that construct a spanning tree within a network of processing entities. Lower bounds and related work are also discussed.

2003

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on the sparsifier size are not known, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs. Our main contribution is the first algorithm for constructing epsilon-spectral sparsifiers for hyper-graphs with O*(n) hyperedges, where O* suppresses (epsilon(-1) log n)(O(1)) factors. This bound is independent of the rank r (maximum cardinality of a hyperedge), and is essentially best possible due to a recent bit complexity lower bound of Omega(nr) for hypergraph sparsification. This result is obtained by introducing two new tools. First, we give a new proof of spectral concentration bounds for sparsifiers of graphs; it avoids linear-algebraic methods, replacing e.g. the usual application of the matrix Bernstein inequality and therefore applies to the (nonlinear) hypergraph setting. To achieve the result, we design a new sequence of hypergraphdependent epsilon-nets on the unit sphere in R-n. Second, we extend the weight-assignment technique of Chen, Khanna and Nagda [FOCS'20] to the spectral sparsification setting. Surprisingly, the number of spanning trees after the weight assignment can serve as a potential function guiding the reweighting process in the spectral setting.

IEEE COMPUTER SOC2022

Exponential extinction time of the contact process on finite graphs

Thomas Mountford, Jean-Christophe Mourrat, Daniel Rodrigues Valesin

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degree bounded by a given number, the expectation of tau grows exponentially with the number of vertices. Additionally, for any increasing sequence of trees of bounded degree, t divided by its expectation converges in distribution to the unitary exponential distribution. These results also hold if one considers a sequence of graphs having spanning trees with uniformly bounded degree, and provide the basis for powerful coarse-graining arguments. To demonstrate this, we consider the contact process on a random graph with vertex degrees following a power law. Improving a result of Chatterjee and Durrett (2009), we show that, for any non-zero infection rate, the extinction time for the contact process on this graph grows exponentially with the number of vertices. (C) 2016 Elsevier B.V. All rights reserved.

Elsevier Science Bv2016