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

DOI10.1016/J.COR.2016.12.005zbMATH Open1391.90604OpenAlexW2561587777WikidataQ56524193 ScholiaQ56524193MaRDI QIDQ1652247FDOQ1652247

Luis Gouveia, L. Simonetti

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

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.

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)

Cites Work

• Title not available (Why is that?)
• A short note on the approximability of the maximum leaves spanning tree problem
• The regenerator location problem
• An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
• The maximum-leaf spanning tree problem: Formulations and facets
• Title not available (Why is that?)
• 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
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming
• Flow-based formulation for the maximum leaf spanning tree problem
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Reformulation by Intersection Method on the MST Problem with Lower Bound on the Number of Leaves
• Minimal spanning trees with a constraint on the number of leaves
• An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
• Title not available (Why is that?)

Cited In (4)

• Branch‐and‐cut algorithms for the ‐arborescence star problem
• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• A personalized walking bus service requiring optimized route decisions: a real case
• 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

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