
We propose constant-time algorithms for approximating the weight of the maximum weight branching in the general graph model. A directed graph is called a {\it branching} if it is a cyclic and each vertex has at most one incoming edge. An edge-weighted digraph $G$, in which weights are given in real values in $[0, 1]$, of average degree $d$ is given as an oracle access, and we are allowed to ask degrees and incoming edges for every vertex through the oracle. Then, with high probability, our algorithm estimates the weight of the maximum weight branching in $G$ with an absolute error of at most $\varepsilon n$ with query complexity $O(d/\varepsilon^3)$, where $n$ is the number of vertices. We also show a lower bound of $\Omega(d / \varepsilon^2)$. Additionally, our algorithm can be modified to run with query complexity $O(1 / \varepsilon^4)$ for unweighted digraphs, i.e., it runs in time independent of the input size even for digraphs with $\Omega(n^2)$ edges. In contrast, we show that it requires $\Omega(n)$ queries to approximate the weight of the minimum (or maximum) spanning arborescence in a weighted digraph.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
