My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Algorithms

Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum


Reply
 
LinkBack Thread Tools Display Modes
February 6th, 2018, 09: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
idankin is offline  
 

My Computer Forum is free to register and we welcome everyone!

Reply

  My Computer Forum > Computer Science Forum > Algorithms

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 02:15 PM
decide if a graph contains a triangle becko Algorithms 2 December 28th, 2011 12:50 PM
Finding an acyclic orientation in a graph Anonymous Coward Algorithms 7 January 24th, 2010 01:28 PM
How to weight the data? cknapp Algorithms 9 April 29th, 2008 07:42 PM





Copyright © 2018 My Computer Forum Forum. All rights reserved.