Geodesic
An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 272-280

Voir la notice de l'article provenant de la source Math-Net.Ru

A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the number of cycles and a lower bound on the number of edges in each cycle. We suggest a polynomial-time algorithm for solving this problem in the geometric case when the vertices of the graph are points in a multidimensional real space and the distances between them are induced by a positively homogeneous function whose unit ball is an arbitrary convex polytope with a fixed number of facets. The obtained result extends the ideas underlying the well-known algorithm for the polyhedral Max TSP.
Keywords: cycle cover, Max TSP, polyhedral metric
Mots-clés : optimal solution, polynomial-time algorithm. 
@article{TIMM_2018_24_3_a23,
     author = {V. V. Shenmaier},
     title = {An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {272--280},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a23/}
}
TY  - JOUR
AU  - V. V. Shenmaier
TI  - An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 272
EP  - 280
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a23/
LA  - ru
ID  - TIMM_2018_24_3_a23
ER  - 
%0 Journal Article
%A V. V. Shenmaier
%T An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 272-280
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a23/
%G ru
%F TIMM_2018_24_3_a23
V. V. Shenmaier. An algorithm for the polyhedral cycle cover problem with restrictions on the number and length of cycles. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 272-280. http://geodesic.mathdoc.fr/item/TIMM_2018_24_3_a23/