Separating Sublinear Time Computations by Approximate Diameter

DOI10.1007/978-3-540-85097-7_8MaRDI QIDQ5505645zbMATH OpenOpenAlexFDO

Authors Bin Fu, Zhiyu Zhao

Publication date 27 January 2009

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

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Separating sublinear time computations by approximate diameter
• Sublinear time algorithms for metric space problems
• Computing diameter in the streaming and sliding-window models
• Networks cannot compute their diameter in sublinear time
• On approximating metric 1-median in sublinear time

Cites work

• Approximating Average Parameters of Graphs
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Automata, Languages and Programming
• Estimating the weight of metric minimum spanning trees in sublinear-time
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1241385 (Why is no real title available?)
• scientific article; zbMATH DE number 1792102 (Why is no real title available?)
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• On testing expansion in bounded-degree graphs
• Property testing and its connection to learning and approximation
• Sublinear Geometric Algorithms
• Sublinear time width-bounded separators and their application to the protein side-chain packing problem

Cited in

(3)

• Computability of width of submodular partition functions
• scientific article; zbMATH DE number 7053319 (Why is no real title available?)
• Separating sublinear time computations by approximate diameter

This page was built for publication: Separating Sublinear Time Computations by Approximate Diameter

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