Hi, Everyone:
This email tries to clear up a message that I sent to
this list before
titled "enumeration of all strongly connected
subgraphs" for research issues
on online community relationship. Thanks for many ones
who replied and made me realize that I did not make my
problem statement clear.
Hope the following does the job.
I need an efficient algorithm for generating all
possible mutually reachable
subgraphs (i.e., a subgraph that has a path between
any pair of vertices in
both directions) of a given directed graph. It is very
different from the
conventional SCC decomposition of a directed graph,
because that only gives a few SCCs,
not all of the possible mutually reachable subgraphs,
although there are closely
related. For a given directed graph, it may have large
number (even exponential) of
such overlapping subgraphs. A mutually reachable
subgraph may also have a subgraph
which is mutually reachable itself. I need to
enumerate all possible ones, in what ever
combinations of edges and vertices, as long as they
are not isomorphic with each other.
What I mean by being efficient is hopefully the
algorithm complexity is
linear with respect to (V + E) multiplied by the total
number of such subgraphs,
where V is the number of vertices and E is the number
of edges in the given
directed graph.
If you don't have solution for directed graph, but
know an algorithm for generating
all possible connected subgraphs of a given undirected
graph, that will
do too. This algorithm can help classify relationship
of online communities
with each other. For example, how book reading clubs
are related with Amazon.com's
affiliate program, with modeling using graph (node as
community
and edge as relationship between two nodes). Hope this
at least make the problem
statement clear.
Sincere thanks in advance!
--Min
=====
__________________________________________________
Do You Yahoo!?
Bid and sell for free at http://auctions.yahoo.com
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|