Approximating all-points furthest pairs and maximum spanning trees in metric spaces

DOI10.1142/S0129054123500181MaRDI QIDQ6569899zbMATH OpenFDO

Authors Ching-Lueh Chang, Chunwei Chang

Publication date 9 July 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054123500181

zbMATH Keywords

metric spacessublinear algorithmseccentricitiesmaximum spanning trees

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx)

Recommendations

• Sublinear time algorithms for metric space problems
• scientific article; zbMATH DE number 177542
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Minimum Spanning Trees in k-Dimensional Space
• Minimum spanning trees in d dimensions

Cites work

• scientific article; zbMATH DE number 3539473 (Why is no real title available?)
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Better approximation algorithms for the graph diameter
• Spanning Trees and Optimization Problems
• Sublinear time algorithms for metric space problems
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

This page was built for publication: Approximating all-points furthest pairs and maximum spanning trees in metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6569899)