ok, can anybody indicate an algorithm that would verify if there exists
a set of k independent vertices in a graph ?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Problem
Consider two sorted arrays of arbitary size, The aim is to find k minimum
sums with the condition that there must be elements from both
arrays in each sum. What is the best possible way to do this o(klogk) ?
example input
array1 = [1,2,3,4,5,6,7]
array2= [3,4,7,9,15,17,25]
find 3
I've found an implementation that uses whether bc is a 'right turn'
from ab as its sole corvergence criterion (where a b and c are sites
in neighboring regions). The code it uses is:
if ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) 0)
--~--~-~--~~~---~--~~
You
I just tested it . . .right turn detection did the trick. so there's
your answer.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
I think O(klogk) is possible.
array1=A={a1,a2,...,},B=arrary2={b1,b2,..}
think about the 2-d grid generated by A,B ( all points (ai,bj)).
using a swap line x+y=c, swap these point until we have scaned k point.
maintain a heap to tell which point will be the next point we will
scan.
Moreover, if
The problem is infact finding the lowest numbers of the combined
arrays. For that you can use concept of merge algorithm of the merge
sort. That will work out in only O(nlogn) time.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
On Nov 28, 10:27 pm, Andre [EMAIL PROTECTED] wrote:
Hi,
I was thinking to do something like this, but is it an efficient way to
do it?
Do you know any well know algorithm to do this kind of thing?
Thanks,
Andre
U can use a maximum heap based on prority and
decrease priority after