The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Converting an adjacency list into partitioning..help needed
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 5 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Oct 11 2005, 2:51 am
From: "Karthik" <kjkar...@gmail.com>
Date: Mon, 10 Oct 2005 23:51:58 -0700
Local: Tues, Oct 11 2005 2:51 am
Subject: Converting an adjacency list into partitioning..help needed
HI guys,

I have encountered a problem on converting an adjacency matrix
into partitioning. By partitioning, I mean that they are a collection
of lists in which order and connectivity within a list doesnt
matter..For ex:

Input:
------
A B C D E F
A 0 1 0 0 0 1
B 1 0 0 0 0 0
C 0 0 0 1 0 0
D 0 0 1 0 1 0
E 0 0 0 1 0 0
F 1 0 0 0 0 0

Distinct Pairs : (A,B),(A,F),(C,D),(D,E)

Hence the output shd be :  (A,B,F)
------           (C,D,E)       2 lists

The matrix is essentially a symmetric square matrix in which diagonal
elements are irrelevant.So, only (((N^2)/2) - N) are only stored to
reduce memory.

I have thought of an algorithm doing this job in O(N^3) time and
O(N) in space. Can any suggest me an algorithm better than this
complexity. N is very large for me, so I cant afford O(N^3)..Please
help..

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 11 2005, 5:44 am
From: "Andy Twigg" <andy.tw...@gmail.com>
Date: Tue, 11 Oct 2005 09:44:07 -0000
Local: Tues, Oct 11 2005 5:44 am
Subject: Re: Converting an adjacency list into partitioning..help needed
Why not just use time O(n^2) to construct the connected components of
the graph? This is what you appear to want from your output.

-Andy

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 11 2005, 9:28 am
From: "Karthik" <kjkar...@gmail.com>
Date: Tue, 11 Oct 2005 06:28:17 -0700
Local: Tues, Oct 11 2005 9:28 am
Subject: Re: Converting an adjacency list into partitioning..help needed
I just didnt get ur point really...I want to say that here in the
problem you are not given the pairs, You are only provided with the
square matrix from where you shd derive the lists...Do u want to say
that it is still possible in a O(N^2) time?? If so plz explain..

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 12 2005, 2:06 am
From: "Karthik" <kjkar...@gmail.com>
Date: Tue, 11 Oct 2005 23:06:15 -0700
Local: Wed, Oct 12 2005 2:06 am
Subject: Re: Converting an adjacency list into partitioning..help needed
Can u just describe or send a link to the algorithm which converts
matrix into graph in O(N^2) time.....

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 13 2005, 7:21 am
From: "Andy Twigg" <andy.tw...@gmail.com>
Date: Thu, 13 Oct 2005 11:21:06 -0000
Local: Thurs, Oct 13 2005 7:21 am
Subject: Re: Converting an adjacency list into partitioning..help needed
Doesn't the matrix represent the graph? It is just the adjacency matrix
of the graph..