An exact algorithm for the maximum leaf spanning tree problem.

DOI10.1016/S0305-0548(02)00117-XMaRDI QIDQ1413822zbMATH OpenFDO

Authors Tetsuya Fujie

Publication date 17 November 2003

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

zbMATH Keywords

Integer programmingSpanning treesBranch and bound

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

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
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Spanning Trees with Many Leaves

Cites work

• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• A short note on the approximability of the maximum leaves spanning tree problem
• A threshold of ln n for approximating set cover
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Approximation algorithms for connected dominating sets
• Constructing full spanning trees for cubic graphs
• Minimal spanning trees with a constraint on the number of leaves
• Spanning Trees with Many Leaves
• The maximum-leaf spanning tree problem: Formulations and facets

Cited in

(23)

• scientific article; zbMATH DE number 6611438 (Why is no real title available?)
• Approximation algorithms for the maximum leaf spanning tree problem on acyclic digraphs
• Regenerator location problem: polyhedral study and effective branch-and-cut algorithms
• Finding totally independent spanning trees with linear integer programming
• Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
• The connected domination number of grids
• Spanning trees of totally edge-growing network models
• A branch-and-Benders-cut approach for the fault tolerant regenerator location problem
• On connected dominating sets of restricted diameter
• The regenerator location problem
• scientific article; zbMATH DE number 5777935 (Why is no real title available?)
• Spanning trees with a constraint on the number of leaves. A new formulation
• The maximum-leaf spanning tree problem: Formulations and facets
• An exact solution framework for the minimum cost dominating tree problem
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• An exact algorithm for the maximum leaf spanning tree problem
• Branch‐and‐cut algorithms for the ‐arborescence star problem
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• An exact algorithm for the maximum leaf spanning tree problem
• Flow-based formulation for the maximum leaf spanning tree problem
• On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
• On maximum leaf trees and connections to connected maximum cut problems
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints

This page was built for publication: An exact algorithm 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 Q1413822)