Approximation Algorithms for Generalized MST and TSP in Grid Clusters

DOI10.1007/978-3-319-26626-8_9zbMath1478.90101arXiv1507.04438OpenAlexW882058369MaRDI QIDQ3467839

Binay K. Bhattacharya, Vladyslav Sokol, Akbar Rafiey, Arash Rafiey, Ante Ćustić

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.04438

zbMATH Keywords

approximation algorithmgeneralized minimum spanning treegeneralized travelling salesmangrid clusters

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem, Unnamed Item, Approximation schemes for the generalized traveling salesman problem, Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The geometric generalized minimum spanning tree problem with grid clustering
• A tabu search heuristic for the generalized minimum spanning tree problem
• The traveling salesman problem: An overview of exact and approximate algorithms
• Approximation algorithms for the Geometric Covering Salesman Problem
• Heuristic Search for the Generalized Minimum Spanning Tree Problem
• Some Applications of the Generalized Travelling Salesman Problem
• On the generalized minimum spanning tree problem
• Automata, Languages and Programming
• Algorithms - ESA 2003