Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Distributed Algorithm for Finding Hamiltonian Cycles in Random Graphs in O(log n) Time
44
0
0.0
(
0
)
Added by
Volker Turau
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Volker Turau
Ask ChatGPT about the research
No Arabic abstract
It is known for some time that a random graph $G(n,p)$ contains w.h.p. a Hamiltonian cycle if $p$ is larger than the critical value $p_{crit}= (log n + log log n + omega_n)/n$. The determination of a concrete Hamiltonian cycle is even for values much larger than $p_{crit}$ a nontrivial task. In this paper we consider random graphs $G(n,p)$ with $p$ in $tilde{Omega}(1/sqrt{n})$, where $tilde{Omega}$ hides poly-logarithmic factors in $n$. For this range of $p$ we present a distributed algorithm ${cal A}_{HC}$ that finds w.h.p. a Hamiltonian cycle in $O(log n)$ rounds. The algorithm works in the synchronous model and uses messages of size $O(log n)$ and $O(log n)$ memory per node.
rate research
Read More
In population protocols, the underlying distributed network consists of $n$ nodes (or agents), denoted by $V$, and a scheduler that continuously selects uniformly random pairs of nodes to interact. When two nodes interact, their states are updated by applying a state transition function that depends only on the states of the two nodes prior to the interaction. The efficiency of a population protocol is measured in terms of both time (which is the number of interactions until the nodes collectively have a valid output) and the number of possible states of nodes used by the protocol. By convention, we consider the parallel time cost, which is the time divided by $n$. In this paper we consider the majority problem, where each node receives as input a color that is either black or white, and the goal is to have all of the nodes output the color that is the majority of the input colors. We design a population protocol that solves the majority problem in $O(log^{3/2}n)$ parallel time, both with high probability and in expectation, while using $O(log n)$ states. Our protocol improves on a recent protocol of Berenbrink et al. that runs in $O(log^{5/3}n)$ parallel time, both with high probability and in expectation, using $O(log n)$ states.
Consider a metric space $(P,dist)$ with $N$ points whose doubling dimension is a constant. We present a simple, randomized, and recursive algorithm that computes, in $O(N log N)$ expected time, the closest-pair distance in $P$. To generate recursive calls, we use previous results of Har-Peled and Mendel, and Abam and Har-Peled for computing a sparse annulus that separates the points in a balanced way.
Tree comparison metrics have proven to be an invaluable aide in the reconstruction and analysis of phylogenetic (evolutionary) trees. The path-length distance between trees is a particularly attractive measure as it reflects differences in tree shape as well as differences between branch lengths. The distance equals the sum, over all pairs of taxa, of the squared differences between the lengths of the unique path connecting them in each tree. We describe an $O(n log n)$ time for computing this distance, making extensive use of tree decomposition techniques introduced by Brodal et al. (2004).
We show that the geodesic diameter of a polygonal domain with n vertices can be computed in O(n^4 log n) time by considering O(n^3) candidate diameter endpoints; the endpoints are a subset of vertices of the overlay of shortest path maps from vertices of the domain.
We design and implement an efficient parallel algorithm for finding a perfect matching in a weighted bipartite graph such that weights on the edges of the matching are large. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization. Due to the lack of scalable alternatives, distributed solvers use sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then iteratively improves the weight of the perfect matching by searching for weight-increasing cycles of length four in parallel. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
