Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Simple Algorithm for Computing BOCP
179
0
0.0
(
0
)
Added by
Zhijie Wang
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Jack Wang
Ask ChatGPT about the research
No Arabic abstract
In this article, we devise a concise algorithm for computing BOCP. Our method is simple, easy-to-implement but without loss of efficiency. Given two circular-arc polygons with $m$ and $n$ edges respectively, our method runs in $O(m+n+(l+k)log l)$ time, using $O(m+n+k)$ space, where $k$ is the number of intersections, and $l$ is the number of {edge}s. Our algorithm has the power to approximate to linear complexity when $k$ and $l$ are small. The superiority of the proposed algorithm is also validated through empirical study.
rate research
Read More
We show a deterministic algorithm for computing edge connectivity of a simple graph with $m$ edges in $m^{1+o(1)}$ time. Although the fastest deterministic algorithm by Henzinger, Rao, and Wang [SODA17] has a faster running time of $O(mlog^{2}mloglog m)$, we believe that our algorithm is conceptually simpler. The key tool for this simplication is the expander decomposition. We exploit it in a very straightforward way compared to how it has been previously used in the literature.
We study the problem of estimating the edit distance between two $n$-character strings. While exact computation in the worst case is believed to require near-quadratic time, previous work showed that in certain regimes it is possible to solve the following {em gap edit distance} problem in sub-linear time: distinguish between inputs of distance $le k$ and $>k^2$. Our main result is a very simple algorithm for this benchmark that runs in time $tilde O(n/sqrt{k})$, and in particular settles the open problem of obtaining a truly sublinear time for the entire range of relevant $k$. Building on the same framework, we also obtain a $k$-vs-$k^2$ algorithm for the one-sided preprocessing model with $tilde O(n)$ preprocessing time and $tilde O(n/k)$ query time (improving over a recent $tilde O(n/k+k^2)$-query time algorithm for the same problem [GRS20].
Given a graph $G=(V,E)$ and an integer $k ge 1$, a $k$-hop dominating set $D$ of $G$ is a subset of $V$, such that, for every vertex $v in V$, there exists a node $u in D$ whose hop-distance from $v$ is at most $k$. A $k$-hop dominating set of minimum cardinality is called a minimum $k$-hop dominating set. In this paper, we present linear-time algorithms that find a minimum $k$-hop dominating set in unicyclic and cactus graphs. To achieve this, we show that the $k$-dominating set problem on unicycle graph reduces to the piercing circular arcs problem, and show a linear-time algorithm for piercing sorted circular arcs, which improves the best known $O(nlog n)$-time algorithm.
Let $P$ be a path graph of $n$ vertices embedded in a metric space. We consider the problem of adding a new edge to $P$ so that the radius of the resulting graph is minimized, where any center is constrained to be one of the vertices of $P$. Previously, the continuous version of the problem where a center may be a point in the interior of an edge of the graph was studied and a linear-time algorithm was known. Our discrete version of the problem has not been studied before. We present a linear-time algorithm for the problem.
We describe a general purpose algorithm for counting simple cycles and simple paths of any length $ell$ on a (weighted di)graph on $N$ vertices and $M$ edges, achieving a time complexity of $Oleft(N+M+big(ell^omega+ellDeltabig) |S_ell|right)$. In this expression, $|S_ell|$ is the number of (weakly) connected induced subgraphs of $G$ on at most $ell$ vertices, $Delta$ is the maximum degree of any vertex and $omega$ is the exponent of matrix multiplication. We compare the algorithm complexity both theoretically and experimentally with most of the existing algorithms for the same task. These comparisons show that the algorithm described here is the best general purpose algorithm for the class of graphs where $(ell^{omega-1}Delta^{-1}+1) |S_ell|leq |text{Cycle}_ell|$, with $|text{Cycle}_ell|$ the total number of simple cycles of length at most $ell$, including backtracks and self-loops. On ErdH{o}s-Renyi random graphs, we find empirically that this happens when the edge probability is larger than circa $4/N$. In addition, we show that some real-world networks also belong to this class. Finally, the algorithm permits the enumeration of simple cycles and simple paths on networks where vertices are labeled from an alphabet on $n$ letters with a time complexity of $Oleft(N+M+big(n^ellell^omega+ellDeltabig) |S_ell|right)$. A Matlab implementation of the algorithm proposed here is available for download.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
