jakeb@spica.ucsc.edu (Paul) (01/14/90)
I am writing a program in C which will have to manipulate large
numbers of directed graphs. The properties of these graphs
are as follows:
No graph will have more than 45 vertexes.
Each vertex will be one of 15 different colors.
Each edge will be one of 3 different colors.
There will be at most two edges (one in each direction)
between any pair of vertexes.
The graphs are not necessarily connected.
Given these properties, I need *efficient* solutions to the
following problems:
Problem 1: Given two graphs, A and B, determine if A is a
subgraph of B, or vice versa. (A and B isomorphic
should be also be detected.)
Problem 2: Given two graphs, A and B, determine the graph
C that is the maximum common subgraph of A and B.
Alternatively, determine C that is some reasonably large
common subgraph of A and B. If the system works as
planned, the average case will have a large amount of
commonality between A and B.
In both of these problems, vertex and edge color are significant.
(A graph with three red vertexes cannot be a subgraph of a graph
with three blue vertexes.)
I would very much appreciate any information, pointers, comments,
tips, etc. on algorithms to solve these two problems. Solutions
must be appropriate for implementation in "C" - this module must
interface with a lot of already-written code. "C" Code would (of
course) be ideal, but I'd be very happy with a paper or reference to
an appropriate algorithm.
As a side note, I'm planning on using an adjacency matrix as the
graph representaton - does anyone have a better idea?
Post or email - I'll summarize to the net.
_
|] / ...!ucbvax!ucscc!estar!jakeb
| aul /_ ola jakeb@estar.UCSC.EDU