Spanning trees with a constraint on the number of leaves. A new formulation

DOI10.1016/J.COR.2016.12.005MaRDI QIDQ1652247zbMATH OpenOpenAlexWikidataFDO

Authors L. Simonetti, Luis Gouveia

Publication date 11 July 2018

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

Full work available at URL https://doi.org/10.1016/j.cor.2016.12.005

zbMATH Keywords

spanning treescombinatorial optimizationILP reformulationsmax-leaves

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Integer programming (90C10)

Recommendations

• Flow-based formulation for the maximum leaf spanning tree problem
• Reformulation by intersection method on the MST problem with lower bound on the number of leaves
• The maximum-leaf spanning tree problem: Formulations and facets
• Minimal spanning trees with a constraint on the number of leaves
• An exact algorithm for the maximum leaf spanning tree problem.

Cites work

• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• A short note on the approximability of the maximum leaves spanning tree problem
• An exact algorithm for the maximum leaf spanning tree problem
• An exact algorithm for the maximum leaf spanning tree problem.
• An integer programming approach for fault-tolerant connected dominating sets
• Approximation algorithms for connected dominating sets
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Flow-based formulation for the maximum leaf spanning tree problem
• Graph domination, coloring and cliques in telecommunications
• Minimal spanning trees with a constraint on the number of leaves
• Network flows. Theory, algorithms, and applications.
• Reformulation by intersection method on the MST problem with lower bound on the number of leaves
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Solving the connected dominating set problem and power dominating set problem by integer programming
• The maximum-leaf spanning tree problem: Formulations and facets
• The regenerator location problem

Cited in

(6)

• A personalized walking bus service requiring optimized route decisions: a real case
• The maximum-leaf spanning tree problem: Formulations and facets
• Reformulation by intersection method on the MST problem with lower bound on the number of leaves
• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• Branch‐and‐cut algorithms for the ‐arborescence star problem
• Flow-based formulation for the maximum leaf spanning tree problem

This page was built for publication: Spanning trees with a constraint on the number of leaves. A new formulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1652247)