### Abstract

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/logn) 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/log^{2}n) (Hajiaghayi et al., ESA 2015) to Ω(1/logn).

Original language | English (US) |
---|---|

Pages (from-to) | 31-34 |

Number of pages | 4 |

Journal | Information Processing Letters |

Volume | 129 |

DOIs | |

State | Published - Jan 2018 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

### Keywords

- Approximation algorithms
- Connected maximum cut
- Maximum leaf trees

### Cite this

*Information Processing Letters*,

*129*, 31-34. https://doi.org/10.1016/j.ipl.2017.06.002