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

DOI10.1134/S0081543819070113zbMATH Open1441.05095OpenAlexW3012949478MaRDI QIDQ2185648FDOQ2185648

Authors: 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

Recommendations

• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• Constant-factor approximations for cycle cover problems
• On Approximating Restricted Cycle Covers
• scientific article; zbMATH DE number 1947046
• scientific article; zbMATH DE number 1875429

zbMATH Keywords

optimal solutionpolynomial-time algorithmcycle covermaximum traveling salesman problempolyhedral metricmax TSP

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• An optimal strategy for the constrained cycle cover problem
• A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
• A branch-and-cut algorithm for the maximum covering cycle problem
• On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space

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

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