By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,933 Members | 1,264 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,933 IT Pros & Developers. It's quick & easy.

Constructing Quotient Graphs

P: n/a
If we have a graph G=(N,E), where N is the set of nodes, and E is the
set of edges. If we partition N into k parts (partition 1, 2,3...k).
And this partition is given by an array, with the node number as the
index. For example, C[x]=a means node x is belongs to partition a.

We define the "Quotient graph" with respect to the above partition as:

A simple graph with no multiple edges. With the set of nodes 1 to K,
and the set of edges (i,j) such that for each each edge (u,v) in E
(the original set of edges in G), there is C[u]=i and C[v]=j.

In English, the quotient graph is a graph with all the K partition
numbers as the edges.

How can I give an algorithm to construct a Quotient Graph from G, with
running time O(size(N)+size(E)).



Nov 17 '08 #1
Share this Question
Share on Google+
1 Reply


P: n/a
BigBaz wrote:
If we have a graph G=(N,E), where N is the set of nodes, and E is the
set of edges. If we partition N into k parts (partition 1, 2,3...k).
And this partition is given by an array, with the node number as the
index. For example, C[x]=a means node x is belongs to partition a.

We define the "Quotient graph" with respect to the above partition as:

A simple graph with no multiple edges. With the set of nodes 1 to K,
and the set of edges (i,j) such that for each each edge (u,v) in E
(the original set of edges in G), there is C[u]=i and C[v]=j.

In English, the quotient graph is a graph with all the K partition
numbers as the edges.

How can I give an algorithm to construct a Quotient Graph from G, with
running time O(size(N)+size(E)).
a) This is off-topic since it is unrelated to C++.

b) It also smells like homework.

c) When posting to a more topical group, you also might want to specify the
data structure for the graph. If the edges are described as an incidence
matrix, then the input is a size(N) x size(N) matrix and the result is a
size(K) x size(K) matrix. So input and output alone will be worse than
O(size(N)+size(E)).

d) A book on graph algorithms might be a good start.
Best

Kai-Uwe Bux
Nov 17 '08 #2

This discussion thread is closed

Replies have been disabled for this discussion.