Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph

摘要

Some hard-to solve combinatorial problems of finding several disjoint discrete structures in complete weighted graph are considered. Efficient algorithms with performance guarantees are constructed for the Euclidean m-Peripatetic Salesman Problem, m-Weighted Clique Problem and m-Layer Planar three-index Assignment Problem.