On Lower Bounds for the Time and the Bit Complexity of Some Probabilistic Distributed Graph Algorithms - (Extended Abstract).
Allyx FontaineYves MétivierJohn Michael RobsonAkka ZemmariPublished in: SOFSEM (2014)
Keyphrases
- extended abstract
- lower bound
- worst case
- graph theory
- computational complexity
- computational cost
- space complexity
- online algorithms
- high computational complexity
- upper bound
- memory requirements
- random graphs
- learning algorithm
- random walk
- branch and bound algorithm
- error bounds
- generative model
- lower and upper bounds
- probabilistic model
- np hard
- maximum flow
- polynomial time complexity