A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
DOI10.1134/S0081543815050107zbMATH Open1409.05158MaRDI QIDQ492282FDOQ492282
Authors: M. Yu. Khachaĭ, Katherine Neznakhina 
Publication date: 20 August 2015
Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)
Recommendations
- Approximation of Euclidean \(k\)-size cycle cover problem
- Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
- An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
- A polynomial-time approximation scheme for embedding hypergraph in a cycle
- Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
- On approximating maximum covering cycles in undirected graphs
- A Polynomial Time Algorithm for Finding a Cycle Covering a Given Set of Vertices in a Semicomplete Multipartite Digraph
- On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
- scientific article; zbMATH DE number 1223730
- On Approximating Restricted Cycle Covers
traveling salesman problempolynomial-time approximation schemeNP-hard problemcycle cover of size \(k\)
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Abstract computational complexity for mathematical programming problems (90C60) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Quad trees: A data structure for retrieval by composite keys
- The truck dispatching problem
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The vehicle routing problem. Latest advances and new challenges.
- The Euclidean traveling salesman problem is NP-complete
- P-Complete Approximation Problems
- Title not available (Why is that?)
- Efficient algorithms with performance guarantees for some problems of finding several cliques in a complete undirected weighted graph
- Lower bounds for symmetricK-peripatetic salesman problems
- On the asymptotic optimality of an algorithm for solving the maximum \(m\)-PSP in a multidimensional Euclidean space
- Asymptotically optimal algorithm for finding one and two edge-disjoint traveling salesman routes of maximal weight in Euclidean space
- Approximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2
- Title not available (Why is that?)
Cited In (12)
- The Euclidean distance completion problem: cycle completability
- Approximation of Euclidean \(k\)-size cycle cover problem
- An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
- On the asymptotic optimality of a solution of the Euclidean problem of covering a graph by \(m\) nonadjacent cycles of maximum total weight
- Approximation algorithms for multi-robot patrol-scheduling with min-max latency
- Approximability of the minimum-weight \(k\)-size cycle cover problem
- A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
- Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
- An exact algorithm with linear complexity for a problem of visiting megalopolises
- Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
- Randomized approximation scheme for Steiner multi cycle in the Euclidean plane
Uses Software
This page was built for publication: A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q492282)
