کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950796 | 1441033 | 2018 | 4 صفحه PDF | دانلود رایگان |
- We obtain the first logarithmic approximation algorithm for the Maximum Leaf Tree problem with general weights on directed and undirected graphs.
- We show that an α-approximation algorithm for the weighted Maximum Leaf Tree problem leads to an Ω(α)-approximation algorithm for the Connected Maximum Cut problem on general weighted graphs.
- Combined with the previous result, we obtain a logarithmic approximation for the Connected Maximum Cut problem, thus improving upon the Ω(1log2â¡n)-approximation obtained by Hajiaghayi et al. (ESA 2015).
In an instance of the (directed) Max Leaf Tree (MLT) problem we are given a vertex-weighted (di)graph G(V,E,w) and the goal is to compute a subtree with maximum weight on the leaves. The weighted Connected Max Cut (CMC) problem takes in an undirected edge-weighted graph G(V,E,w) and seeks a subset SâV such that the induced graph G[S] is connected and âeâδ(S)w(e) is maximized.We obtain a constant approximation algorithm for MLT when the weights are chosen from {0,1}, which in turn implies a Ω(1/logâ¡n) approximation for the general case. We show that the MLT and CMC problems are related and use the algorithm for MLT to improve the factor for CMC from Ω(1/log2â¡n) (Hajiaghayi et al., ESA 2015) to Ω(1/logâ¡n).
Journal: Information Processing Letters - Volume 129, January 2018, Pages 31-34