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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2018
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 2017 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On maximum leaf trees and connections to connected maximum cut problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי