Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems.

Christoph Meinel Stephan Waack

Published in: MFCS (1995)

Keyphrases

lower bound
computational complexity
decision problems
randomly generated problems
upper bound
np complete
min sum
np hardness
polynomial time complexity
search algorithm
worst case
graph structure
space complexity
graph representation
average case complexity