Flow-based formulation for the maximum leaf spanning tree problem

DOI10.1016/j.endm.2015.07.035zbMath1347.05034OpenAlexW2198010731MaRDI QIDQ324785

M. F. Reis, Orlando Lee, Fábio Luiz Usberti

Publication date: 17 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.035

zbMATH Keywords

combinatorial optimizationvalid inequalitiesmaximum leaf spanning treemaximum leaf spanning arborescence

Mathematics Subject Classification ID

Trees (05C05) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items

Optimization of wireless sensor networks deployment with coverage and connectivity constraints, Spanning trees with a constraint on the number of leaves. A new formulation, A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets, Instance generation framework for green vehicle routing

Cites Work

• Unnamed Item
• Unnamed Item
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Constructing full spanning trees for cubic graphs
• An exact algorithm for the maximum leaf spanning tree problem.
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• The maximum-leaf spanning tree problem: Formulations and facets
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem