Upper and lower bounding procedures for the minimum caterpillar spanning problem

DOI10.1016/j.endm.2009.11.015zbMath1268.05210MaRDI QIDQ2840519

Yuri Frota, Luidi Simonetti, Cid Carvalho De Souza

Publication date: 19 July 2013

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.015

zbMATH Keywords

integer programming; combinatorial optimization; caterpillar trees

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope, The caterpillar-packing polytope, The caterpillar-packing polytope, Branch‐and‐cut algorithms for the ‐arborescence star problem

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search
• The Capacitated m-Ring-Star Problem
• Column Generation Algorithms for the Capacitated m-Ring-Star Problem
• TSPLIB—A Traveling Salesman Problem Library
• The Circuit Polytope: Facets
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• Algorithms and Computation
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs