An exact algorithm for the maximum leaf spanning tree problem.
From MaRDI portal
Publication:1413822
DOI10.1016/S0305-0548(02)00117-XzbMath1047.90056MaRDI QIDQ1413822
Publication date: 17 November 2003
Published in: Computers \& Operations Research (Search for Journal in Brave)
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Optimization of wireless sensor networks deployment with coverage and connectivity constraints ⋮ The connected domination number of grids ⋮ On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem ⋮ Flow-based formulation for the maximum leaf spanning tree problem ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ The regenerator location problem ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ A branch-and-Benders-cut approach for the fault tolerant regenerator location problem ⋮ An exact solution framework for the minimum cost dominating tree problem ⋮ On connected dominating sets of restricted diameter
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constructing full spanning trees for cubic graphs
- Minimal spanning trees with a constraint on the number of leaves
- A short note on the approximability of the maximum leaves spanning tree problem
- A threshold of ln n for approximating set cover
- Spanning Trees with Many Leaves
- Approximating Maximum Leaf Spanning Trees in Almost Linear Time
- The maximum-leaf spanning tree problem: Formulations and facets
- Approximation algorithms for connected dominating sets