home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2746 < prev    next >
Encoding:
Text File  |  1992-12-22  |  1.3 KB  |  38 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!microsoft!hexnut!bobatk
  3. From: bobatk@microsoft.com (Bob Atkinson)
  4. Subject: Wanted: alg for "is G1 a subgraph of G2"
  5. Message-ID: <1992Dec21.230436.17820@microsoft.com>
  6. Date: 21 Dec 92 23:04:36 GMT
  7. Organization: Microsoft Corporation
  8. Lines: 28
  9.  
  10. I have run across the need the need for efficient algorithms for determining
  11. if a given colored directed graph is a subgraph of a second colored directed
  12. graph. If it makes a difference, I expect roughly the following problem
  13. characteristics:
  14.  
  15.     1) the out-degree of each node tends to be small, on 
  16.         the order of ten or so.
  17.     2) the in-degree of each node is almost always one, 
  18.         though there are exceptions.
  19.     3) the number of colors with which nodes are painted 
  20.         is on the order of tens of thousands
  21.     4) the query graph (the first) has tens of nodes, 
  22.         while the target graph may have thousands.
  23.     5) both graphs are very often acyclic. Possibly, I could
  24.         require that this be so, if that were to make an
  25.         otherwise intractable problem tractable.
  26.  
  27. In addition, I am also interested in the related problem where the edges of the graph are labeled. Here I expect that there are
  28.  
  29.     6) on the order of 25 or so distinct edge labels
  30.  
  31. Can anyone point me towards some likely leads?
  32.  
  33. Thank you very much.
  34.  
  35.     Bob Atkinson
  36.     Microsoft Corporation
  37.     206-936-5570, BobAtk@Microsoft.Com
  38.