文章基本信息
- 标题：Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs
- 作者：Mitsuru Kusumoto ; Yuichi Yoshida ; Hiro Ito 等
- 期刊名称：International Journal of Networking and Computing
- 印刷版ISSN：2185-2847
- 出版年度：2014
- 卷号：3
- 期号：2
- 页码：205-216
- 语种：English
- 出版社：International Journal of Networking and Computing
- 摘要：We propose a constant-time algorithm for approximating the weight of the maximum weight branching in the general graph model. A directed graph is called a branching if it is acyclic and each vertex has at most one incoming edge. An edge-weighted digraph G of average degree d whose weights are real values in [0, 1] is given as an oracle access, and we are allowed to ask degrees and incoming edges for any 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 εn with query complexity O(d/ε 3 ), where n is the number of vertices. We also show a lower bound of Ω(d/ε 2 ). Additionally, our algorithm can be modified to run with query complexity O(1/ε 4 ) for unweighted digraphs, i.e., it runs in time independent of the input size even for digraphs with d = Ω(n) edges. In contrast, we show that it requires Ω(n) queries to approximate the weight of the minimum (or maximum) spanning arborescence in a weighted digraph. Â
Loading...
