Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems
Christoph MeinelStephan WaackPublished in: Electron. Colloquium Comput. Complex. (1995)
Keyphrases
- lower bound
- upper bound
- decision problems
- min sum
- tractable cases
- worst case
- randomly generated problems
- average case complexity
- optimal solution
- polynomial time complexity
- np hardness
- graph representation
- graph databases
- space complexity
- communication cost
- communication networks
- branch and bound algorithm
- structured data
- np complete