Separating Sublinear Time Computations by Approximate Diameter

DOI10.1007/978-3-540-85097-7_8zbMath1168.68591OpenAlexW1531571111MaRDI QIDQ5505645

Zhiyu Zhao, Bin Fu

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) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sublinear time width-bounded separators and their application to the protein side-chain packing problem
• On Testing Expansion in Bounded-Degree Graphs
• Property testing and its connection to learning and approximation
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Approximating Average Parameters of Graphs
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Sublinear Geometric Algorithms
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Automata, Languages and Programming