Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Stronger Lower Bound on Parametric Minimum Spanning Trees
74
0
0.0
(
0
)
Added by
David Eppstein
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
David Eppstein
Ask ChatGPT about the research
No Arabic abstract
We prove that, for an undirected graph with $n$ vertices and $m$ edges, each labeled with a linear function of a parameter $lambda$, the number of different minimum spanning trees obtained as the parameter varies can be $Omega(mlog n)$.
rate research
Read More
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is the trival (dimension) bound, $Omega(n^2)$, the best known upper bound is the extended formulation by Wong (1980) of size $O(n^3)$ (also Martin, 1991). In this note we give a nondeterministic communication protocol with cost $log_2(n^2log n)+O(1)$ for the support of the spanning tree slack matrix. This means that the combinatorial lower bounds can improve the trivial lower bound only by a factor of (at most) $O(log n)$.
A distributed proof (also known as local certification, or proof-labeling scheme) is a mechanism to certify that the solution to a graph problem is correct. It takes the form of an assignment of labels to the nodes, that can be checked locally. There exists such a proof for the minimum spanning tree problem, using $O(log n log W)$ bit labels (where $n$ is the number of nodes in the graph, and $W$ is the largest weight of an edge). This is due to Korman and Kutten who describe it in concise and formal manner in [Korman and Kutten 07]. In this note, we propose a more intuitive description of the result, as well as a gentle introduction to the problem.
A complete understanding of real networks requires us to understand the consequences of the uneven interaction strengths between a systems components. Here we use the minimum spanning tree (MST) to explore the effect of weight assignment and network topology on the organization of complex networks. We find that if the weight distribution is correlated with the network topology, the MSTs are either scale-free or exponential. In contrast, when the correlations between weights and topology are absent, the MST degree distribution is a power-law and independent of the weight distribution. These results offer a systematic way to explore the impact of weak links on the structure and integrity of complex networks.
Chemical tagging of stellar debris from disrupted open clusters and associations underpins the science cases for next-generation multi-object spectroscopic surveys. As part of the Galactic Archaeology project TraCD (Tracking Cluster Debris), a preliminary attempt at reconstructing the birth clouds of now phase-mixed thin disk debris is undertaken using a parametric minimum spanning tree (MST) approach. Empirically-motivated chemical abundance pattern uncertainties (for a 10-dimensional chemistry-space) are applied to NBODY6-realised stellar associations dissolved into a background sea of field stars, all evolving in a Milky Way potential. We demonstrate that significant population reconstruction degeneracies appear when the abundance uncertainties approach 0.1 dex and the parameterised MST approach is employed; more sophisticated methodologies will be required to ameliorate these degeneracies.
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem. Our first result is a randomized distributed algorithm that constructs a spanning tree of maximum degree $hat d = O(dlog{n})$. It requires $O((D + sqrt{n}) log^2 n)$ rounds (w.h.p.), where $D$ is the graph diameter, which matches (within log factors) the optimal round complexity for the related minimum spanning tree problem. Our second result refines this approximation factor by constructing a tree with maximum degree $hat d = O(d + log{n})$, though at the cost of additional polylogarithmic factors in the round complexity. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990s, our results are first efficient distributed solutions for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
