Reformulations and solution algorithms for the maximum leaf spanning tree problem

DOI10.1007/s10287-009-0116-5zbMath1198.90380OpenAlexW2083790738MaRDI QIDQ993702

Abilio Lucena, Luidi Simonetti, Nelson F. Maculan

Publication date: 20 September 2010

Published in: Computational Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10287-009-0116-5

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (19)

Optimization of wireless sensor networks deployment with coverage and connectivity constraints ⋮ Flow-based formulation for the maximum leaf spanning tree problem ⋮ The tree-star problem: a formulation and a branch-and-cut algorithm ⋮ The Generalized Regenerator Location Problem ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ A branch-and-cut algorithm for the minimum branch vertices spanning tree problem ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Regenerator Location Problem in Flexible Optical Networks ⋮ Exact Approaches for Network Design Problems with Relays ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ A branch-and-Benders-cut approach for the fault tolerant regenerator location problem ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ On connected dominating sets of restricted diameter

Uses Software

• SteinLib

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Minimal spanning trees with a constraint on the number of leaves
• A short note on the approximability of the maximum leaves spanning tree problem
• Approximation algorithms for connected dominating sets
• An exact algorithm for the maximum leaf spanning tree problem.
• The regenerator location problem
• A dual ascent approach for steiner tree problems on a directed graph
• An integer linear programming approach to the steiner problem in graphs
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• The maximum-leaf spanning tree problem: Formulations and facets
• Solving Steiner tree problems in graphs to optimality
• Matroids and the greedy algorithm
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Improved algorithms for the Steiner problem in networks

This page was built for publication: Reformulations and solution algorithms for the maximum leaf spanning tree problem