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