An exact algorithm for the maximum leaf spanning tree problem.

DOI10.1016/S0305-0548(02)00117-XzbMath1047.90056MaRDI QIDQ1413822

Tetsuya Fujie

Publication date: 17 November 2003

Published in: Computers \& Operations Research (Search for Journal in Brave)

zbMATH Keywords

Integer programmingBranch and boundSpanning trees

Mathematics Subject Classification ID

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