![]() | ![]() |
|
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 N-th 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 | |
|
![]() | ||||
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 |