Reformulations and solution algorithms for the maximum leaf spanning tree problem

DOI10.1007/S10287-009-0116-5zbMATH Open1198.90380OpenAlexW2083790738MaRDI QIDQ993702FDOQ993702

Nelson Maculan, Abilio Lucena, L. Simonetti

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)

Cites Work

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

Cited In (24)

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

Uses Software

• SteinLib

   Recommendations

• The maximum-leaf spanning tree problem: Formulations and facets 👍 👎
• An exact algorithm for the maximum leaf spanning tree problem 👍 👎
• An exact algorithm for the maximum leaf spanning tree problem 👍 👎
• An exact algorithm for the maximum leaf spanning tree problem. 👍 👎
• An approximation algorithm for the maximum leaf spanning arborescence problem 👍 👎
• Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs 👍 👎
• Flow-based formulation for the maximum leaf spanning tree problem 👍 👎
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time 👍 👎
• On the approximability of some maximum spanning tree problems 👍 👎

This page was built for publication: Reformulations and solution algorithms 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 Q993702)