Nth smallest weight in complete graph

idankin · February 6th, 2018, 08:16 AM

Hi,

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

February 6th, 2018, 08:16 AM	#1
idankin Junior Member Joined: Feb 2018 Posts: 1	Nth smallest weight in complete graph Hi, 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

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Find interval with the smallest variance in sequence	keram	Algorithms	0	March 10th, 2014 01:15 PM
decide if a graph contains a triangle	becko	Algorithms	2	December 28th, 2011 11:50 AM
Finding an acyclic orientation in a graph	Anonymous Coward	Algorithms	7	January 24th, 2010 12:28 PM
How to weight the data?	cknapp	Algorithms	9	April 29th, 2008 06:42 PM