On the longest spanning tree with neighborhoods

DOI10.1007/978-3-319-78455-7_2zbMath1446.68114arXiv1712.03297OpenAlexW2964284126MaRDI QIDQ777263

Adrian Dumitrescu, Ke Chen

Publication date: 7 July 2020

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmneighborhoodgeometric networkmetric problemmaximum (longest) spanning tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Long non-crossing configurations in the plane
• Computing Euclidean maximum spanning trees
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Approximation algorithms for the Geometric Covering Salesman Problem
• On minimum- and maximum-weight minimum spanning trees with neighborhoods
• The geometric maximum traveling salesman problem
• A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets
• Maximum distance between two sets of points in Ed
• Efficient algorithms for computing the maximum distance between two finite planar sets
• Minimum Spanning Tree with Neighborhoods
• Maximum plane trees in multipartite geometric graphs
• An optimal deterministic algorithm for computing the diameter of a three-dimensional point set