Approximability of the minimum Steiner cycle problem

MaRDI QIDQ2970259zbMATH OpenFDO

Authors Monika Steinová

Publication date 29 March 2017

zbMATH Keywords

approximationcycleSteiner treeterminalsTSP

Mathematics Subject Classification ID

Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• The Steiner cycle polytope
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem on graphs: inapproximability results
• Minimum-Weight Cycle Covers and Their Approximability

Cited in

(12)

• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• The Steiner cycle polytope
• The Steiner cycle and path cover problem on interval graphs
• Quasilinear approximation scheme for Steiner multi cycle in the Euclidean plane
• The multiple Steiner TSP with order constraints: complexity and optimization algorithms
• Randomized approximation scheme for Steiner multi cycle in the Euclidean plane
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• Steiner problems with limited number of branching nodes
• Directed Steiner trees with diffusion costs
• Approximations for the Steiner multicycle problem
• A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
• On the restricted Steiner multi cycle problem

This page was built for publication: Approximability of the minimum Steiner cycle problem

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