Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the minimum spanning tree problem in imprecise set-up
73
0
0.0
(
0
)
Added by
Sanjana Dey
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this article, we study the Euclidean minimum spanning tree problem in an imprecise setup. The problem is known as the emph{Minimum Spanning Tree Problem with Neighborhoods} in the literature. We study the problem where the neighborhoods are represented as non-crossing line segments. Given a set ${cal S}$ of $n$ disjoint line segments in $I!!R^2$, the objective is to find a minimum spanning tree (MST) that contains exactly one end-point from each segment in $cal S$ and the cost of the MST is minimum among $2^n$ possible MSTs. We show that finding such an MST is NP-hard in general, and propose a $2alpha$-factor approximation algorithm for the same, where $alpha$ is the approximation factor of the best-known approximation algorithm to compute a minimum cost Steiner tree in an undirected graph with non-negative edge weights. As an implication of our reduction, we can show that the unrestricted version of the problem (i.e., one point must be chosen from each segment such that the cost of MST is as minimum as possible) is also NP-hard. We also propose a parameterized algorithm for the problem based on the separability parameter defined for segments.
rate research
Read More
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A emph{red-blue-purple spanning graph} (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast $(frac 12rho+1)$-approximation algorithm, where $rho$ is the Steiner ratio.
We present a novel self-stabilizing algorithm for minimum spanning tree (MST) construction. The space complexity of our solution is $O(log^2n)$ bits and it converges in $O(n^2)$ rounds. Thus, this algorithm improves the convergence time of all previously known self-stabilizing asynchronous MST algorithms by a multiplicative factor $Theta(n)$, to the price of increasing the best known space complexity by a factor $O(log n)$. The main ingredient used in our algorithm is the design, for the first time in self-stabilizing settings, of a labeling scheme for computing the nearest common ancestor with only $O(log^2n)$ bits.
In this paper, we address the minimum-area rectangular and square annulus problem, which asks a rectangular or square annulus of minimum area, either in a fixed orientation or over all orientations, that encloses a set $P$ of $n$ input points in the plane. To our best knowledge, no nontrivial results on the problem have been discussed in the literature, while its minimum-width variants have been intensively studied. For a fixed orientation, we show reductions to well-studied problems: the minimum-width square annulus problem and the largest empty rectangle problem, yielding algorithms of time complexity $O(nlog^2 n)$ and $O(nlog n)$ for the rectangular and square cases, respectively. In arbitrary orientation, we present $O(n^3)$-time algorithms for the rectangular and square annulus problem by enumerating all maximal empty rectangles over all orientations. The same approach is shown to apply also to the minimum-width square annulus problem and the largest empty square problem over all orientations, resulting in $O(n^3)$-time algorithms for both problems. Consequently, we improve the previously best algorithm for the minimum-width square annulus problem by a factor of logarithm, and present the first algorithm for the largest empty square problem in arbitrary orientation. We also consider bicriteria optimization variants, computing a minimum-width minimum-area or minimum-area minimum-width annulus.
We present time-space trade-offs for computing the Euclidean minimum spanning tree of a set $S$ of $n$ point-sites in the plane. More precisely, we assume that $S$ resides in a random-access memory that can only be read. The edges of the Euclidean minimum spanning tree $text{EMST}(S)$ have to be reported sequentially, and they cannot be accessed or modified afterwards. There is a parameter $s in {1, dots, n}$ so that the algorithm may use $O(s)$ cells of read-write memory (called the workspace) for its computations. Our goal is to find an algorithm that has the best possible running time for any given $s$ between $1$ and $n$. We show how to compute $text{EMST}(S)$ in $Obig((n^3/s^2)log s big)$ time with $O(s)$ cells of workspace, giving a smooth trade-off between the two best known bounds $O(n^3)$ for $s = 1$ and $O(n log n)$ for $s = n$. For this, we run Kruskals algorithm on the relative neighborhood graph (RNG) of $S$. It is a classic fact that the minimum spanning tree of $text{RNG}(S)$ is exactly $text{EMST}(S)$. To implement Kruskals algorithm with $O(s)$ cells of workspace, we define $s$-nets, a compact representation of planar graphs. This allows us to efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
