Nth smallest weight in complete graph

Feb 2018

I have a complete graph with N vertices, with positive weights assigned to their edges.

Each node knows the weight of its edges.

Each node has a unique ID.

We can send message on each edge, one message per stage per direction. message size is constant, independently from N.

All weights are unique and positive integer.

The algorithm should find the N-th lightest weight in the graph. We search for a probability algorithm with expected runtime of O(1) stages.

Thanks for helping
Similar Discussions Computer Science Forum Date
Data Structures / Algorithms