ﻻ يوجد ملخص باللغة العربية
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.
A new efficient algorithm is presented for finding all simple cycles that satisfy a length constraint in a directed graph. When the number of vertices is non-trivial, most cycle-finding problems are of practical interest for sparse graphs only. We sh
In the subgraph counting problem, we are given a input graph $G(V, E)$ and a target graph $H$; the goal is to estimate the number of occurrences of $H$ in $G$. Our focus here is on designing sublinear-time algorithms for approximately counting occurr
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)$ tim
We propose a simple iterative (SI) algorithm for the maxcut problem through fully using an equivalent continuous formulation. It does not need rounding at all and has advantages that all subproblems have explicit analytic solutions, the cut values ar
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