Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDegree Bounded Bottleneck Spanning Trees in Three Dimensions
69
0
0.0
(
0
)
Added by
Patrick Andersen
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The geometric $delta$-minimum spanning tree problem ($delta$-MST) is the problem of finding a minimum spanning tree for a set of points in a normed vector space, such that no vertex in the tree has a degree which exceeds $delta$, and the sum of the lengths of the edges in the tree is minimum. The similarly defined geometric $delta$-minimum bottleneck spanning tree problem ($delta$-MBST), is the problem of finding a degree bounded spanning tree such that the length of the longest edge is minimum. For point sets that lie in the Euclidean plane, both of these problems have been shown to be NP-hard for certain specific values of $delta$. In this paper, we investigate the $delta$-MBST problem in $3$-dimensional Euclidean space and $3$-dimensional rectilinear space. We show that the problems are NP-hard for certain values of $delta$, and we provide inapproximability results for these cases. We also describe new approximation algorithms for solving these $3$-dimensional variants, and then analyse their worst-case performance.
rate research
Read More
Given a set $P$ of $n$ red and blue points in the plane, a emph{planar bichromatic spanning tree} of $P$ is a spanning tree of $P$, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree $T$, such that the length of the longest edge in $T$ is minimized. In this paper, we show that this problem is NP-hard for points in general position. Moreover, we present a polynomial-time $(8sqrt{2})$-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck $lambda$ can be converted to a planar bichromatic spanning tree of bottleneck at most $8sqrt{2}lambda$.
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.
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $lceil (n+5)/6rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
Given a set of points in the Euclidean plane, the Euclidean textit{$delta$-minimum spanning tree} ($delta$-MST) problem is the problem of finding a spanning tree with maximum degree no more than $delta$ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean textit{$delta$-minimum bottleneck spanning tree} ($delta$-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When $delta leq 4$, these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested.
Let $V$ be a finite set of vertices in the plane and $S$ be a finite set of polygonal obstacles, where the vertices of $S$ are in $V$. We show how to construct a plane $2$-spanner of the visibility graph of $V$ with respect to $S$. As this graph can have unbounded degree, we modify it in three easy-to-follow steps, in order to bound the degree to $7$ at the cost of slightly increasing the spanning ratio to 6.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
