On maximum leaf trees and connections to connected maximum cut problems

Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Manish Purohit, Kanthi Sarpatwar

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


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).

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)31-34
عدد الصفحات4
دوريةInformation Processing Letters
مستوى الصوت129
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 2018
منشور خارجيًانعم

ملاحظة ببليوغرافية

Publisher Copyright:
© 2017 Elsevier B.V.


أدرس بدقة موضوعات البحث “On maximum leaf trees and connections to connected maximum cut problems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا