Exact approaches for the minimum subgraph diameter problem

DOI10.1016/J.COR.2022.106050MaRDI QIDQ2108148zbMATH OpenOpenAlexFDO

Authors Arthur Pratti Dadalto, Fábio Luiz Usberti, Mário César San Felice

Publication date 19 December 2022

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

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

zbMATH Keywords

benchmark instancesbranch-and-cutcombinatorial optimizationinteger linear programmingnetwork design

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• Solving diameter-constrained minimum spanning tree problems by constraint programming
• Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
• Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem
• The Steiner tree problem with delays: a compact formulation and reduction procedures
• Approximating the degree-bounded minimum diameter spanning tree problem

Cites work

• General network design: a unified view of combined location and network design problems
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• Network flows. Theory, algorithms, and applications.
• New benchmark instances for the capacitated vehicle routing problem
• Optimum Communication Spanning Trees
• The complexity of designing a network with minimum diameter
• The complexity of the network design problem
• The non-approximability of bicriteria network design problems
• Two algorithms for constructing a Delaunay triangulation

Cited in

(6)

• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Optimal approximation algorithms for maximum distance-bounded subgraph problems
• Minimizing branching vertices in distance-preserving subgraphs
• scientific article; zbMATH DE number 4029292 (Why is no real title available?)
• Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems
• Knowledge graph based question-answering model with subgraph retrieval optimization

Describes a project that uses

Uses Software

• Gurobi

This page was built for publication: Exact approaches for the minimum subgraph diameter problem

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