Upper and lower bounding procedures for the minimum caterpillar spanning problem

DOI10.1016/J.ENDM.2009.11.015MaRDI QIDQ2840519zbMATH OpenOpenAlexFDO

Authors L. Simonetti, Y. Frota, 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

caterpillar treescombinatorial optimizationinteger programming

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
• The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm
• Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem
• On the minimum caterpillar problem in digraphs
• Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars

Cites work

• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Algorithms and Computation
• Column Generation Algorithms for the Capacitated m-Ring-Star Problem
• scientific article; zbMATH DE number 1375584 (Why is no real title available?)
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Optimizing a ring-based private line telecommunication network using tabu search
• The Capacitated m-Ring-Star Problem
• The Circuit Polytope: Facets
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(9)

• The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
• Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
• A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
• On the minimum caterpillar problem in digraphs
• 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
• A general cut-generating strategy for the caterpillar-packing polytope

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Upper and lower bounding procedures for the minimum caterpillar spanning problem

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