An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles

DOI10.1134/S0081543819070113zbMath1441.05095OpenAlexW3012949478MaRDI QIDQ2185648

V. V. Shenmaier

Publication date: 5 June 2020

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0081543819070113

zbMATH Keywords

polynomial-time algorithmoptimal solutioncycle covermaximum traveling salesman problempolyhedral metricmax TSP

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• Unnamed Item
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• Complexity and approximation of the smallest \(k\)-enclosing ball problem
• Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP
• Approximating maximum weight cycle covers in directed graphs with weights zero and one
• TSP with bounded metrics
• The geometric maximum traveling salesman problem
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem
• Approximation and Online Algorithms

This page was built for publication: An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles