
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
February 6th, 2018, 08:16 AM  #1 
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 Nth lightest weight in the graph. We search for a probability algorithm with expected runtime of O(1) stages. Thanks for helping 
My Computer Forum is free to register and we welcome everyone! 

Tags 
complete, graph, nth, smallest, weight 
Thread Tools  
Display Modes  

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 