Separating sublinear time computations by approximate diameter

DOI10.1007/s10878-009-9248-3zbMath1206.90140OpenAlexW2796755244MaRDI QIDQ849140

Zhiyu Zhao, Bin Fu

Publication date: 24 February 2010

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9248-3

zbMATH Keywords

randomizationdiameterseparation of complexity classessublinear time algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item