What people are saying - Write a review
We haven't found any reviews in the usual places.
Improved Approximation Algorithms for Uniform Connectivity Problems
A ConstantFactor Approximation for the kMST Problem in the Plane
A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability
38 other sections not shown
Other editions - View all
adversary Alice apply approximation algorithms assume bits boolean boolean functions branching program cell probe model complexity components Computer Science connected consider constant construct copy Corollary corresponding defined definition denote deque deterministic disjoint paths document edges efficient elements encryption exists expander graphs factor finite function given graph G implies incremental input integer key distribution label leaf label least Lemma length linear lower bound machine Markov chains matroid node obtain operations optimal oracle output packet pair partial broadcast permutation planar graphs polynomial position prob probabilistic probability probe problem Proc proof protocol prove query queue random recursive result rithm round routing scheme sequence session key simulation sorting sorting network step STOC stopping rule strategy string subgraph subset Symposium tag-tree techniques Theorem Theory tion tree upper bound variables VC dimension vector vertex vertices