Flow-based formulation for the maximum leaf spanning tree problem

DOI10.1016/J.ENDM.2015.07.035MaRDI QIDQ324785zbMATH OpenOpenAlexFDO

Authors 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 optimizationmaximum leaf spanning arborescencemaximum leaf spanning treevalid inequalities

Mathematics Subject Classification ID

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

Recommendations

• The maximum-leaf spanning tree problem: Formulations and facets
• An exact algorithm for the maximum leaf spanning tree problem.
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Spanning trees with a constraint on the number of leaves. A new formulation
• An exact algorithm for the maximum leaf spanning tree problem

Cites work

• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• An exact algorithm for the maximum leaf spanning tree problem.
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Constructing full spanning trees for cubic graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Solving the connected dominating set problem and power dominating set problem by integer programming
• The maximum-leaf spanning tree problem: Formulations and facets

Cited in

(6)

• Spanning trees with a constraint on the number of leaves. A new formulation
• Instance generation framework for green vehicle routing
• The maximum-leaf spanning tree problem: Formulations and facets
• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints
• Reformulations and solution algorithms for the maximum leaf spanning tree problem

This page was built for publication: Flow-based formulation for the maximum leaf spanning tree problem

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