Xref: utzoo comp.theory:197 comp.lang.c:25127
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!snorkelwacker!apple!agate!saturn!spica.ucsc.edu!jakeb
From: jakeb@spica.ucsc.edu (Paul)
Newsgroups: comp.theory,comp.lang.c
Subject: Graph matching algorithms wanted
Keywords: subgraph isomorphisim common maximal
Message-ID: <10312@saturn.ucsc.edu>
Date: 14 Jan 90 13:09:13 GMT
Sender: usenet@saturn.ucsc.edu
Reply-To: jakeb@spica.ucsc.edu (Paul)
Organization: University of California, Santa Cruz
Lines: 43

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