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

DOI10.1016/j.cor.2016.12.005zbMath1391.90604OpenAlexW2561587777WikidataQ56524193 ScholiaQ56524193MaRDI QIDQ1652247

Luidi Simonetti, Luís 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

combinatorial optimizationspanning treesILP reformulationsmax-leaves

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) 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)

Related Items (3)

A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets ⋮ Branch‐and‐cut algorithms for the ‐arborescence star problem ⋮ A personalized walking bus service requiring optimized route decisions: a real case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Flow-based formulation for the maximum leaf spanning tree problem
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Minimal spanning trees with a constraint on the number of leaves
• A short note on the approximability of the maximum leaves spanning tree problem
• Approximation algorithms for connected dominating sets
• An exact algorithm for the maximum leaf spanning tree problem.
• Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• The regenerator location problem
• Reformulation by Intersection Method on the MST Problem with Lower Bound on the Number of Leaves
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
• The maximum-leaf spanning tree problem: Formulations and facets

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