On maximum leaf trees and connections to connected maximum cut problems

DOI10.1016/J.IPL.2017.06.002MaRDI QIDQ2410577zbMATH OpenOpenAlexFDO

Authors Rajiv Gandhi, Mohammad T. Hajiaghayi, Guy Kortsarz, Manish Purohit, Kanthi K. Sarpatwar

Publication date 18 October 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.06.002

zbMATH Keywords

approximation algorithmsconnected maximum cutmaximum leaf trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• An exact algorithm for the maximum leaf spanning tree problem.
• The maximum-leaf spanning tree problem: Formulations and facets
• Kernelization for maximum leaf spanning tree with positive vertex weights

Cites work

• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A short note on the approximability of the maximum leaves spanning tree problem
• An approximation algorithm for the maximum leaf spanning arborescence problem
• Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Mathematical Foundations of Computer Science 2003
• Max-cut under graph constraints
• On finding directed trees with many leaves
• Spanning Trees with Many Leaves
• The polymatroid Steiner problems

Cited in

(3)

• On the bond polytope
• Computing the largest bond and the maximum connected cut of a graph
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems

This page was built for publication: On maximum leaf trees and connections to connected maximum cut problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410577)