BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Mihelič Jurij (University of Ljubljana, Slovenia), Fürst Luka (University of Ljubljana, Slovenia), Čibej Uroš (University of Ljubljana, Slovenia)
Exploratory Equivalence in Graphs: Definition and Algorithms
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 447 - 456, rys., bibliogr. 16 poz.
Grafy, Algorytmy, Analiza matematyczna
Graphs, Algorithms, Mathematical analysis
Motivated by improving the efficiency of pattern matching on graphs, we define a new kind of equivalence on graph vertices. Since it can be used in various graph algorithms that explore graphs, we call it exploratory equivalence. The equivalence is based on graph automorphisms. Because many similar equivalences exist (some also based on automorphisms), we argue that this one is novel. For each graph, there are many possible exploratory equivalences, but for improving the efficiency of the exploration, some are better than others. To this end, we define a goal function that models the reduction of the search space in such algorithms. We describe two greedy algorithms for the underlying optimization problem. One is based directly on the definition using a straightforward greedy criterion, whereas the second one uses several practical speedups and a different greedy criterion. Finally, we demonstrate the huge impact of exploratory equivalence on a real application, i.e, graph grammar parsing.(original abstract)
Full text
  1. Agrafiotis D. K., Lobanov V. S., Shemanarev M., Rassokhin D. N., Izrailev S., Jaeger E. P., Alex S., and Farnum M., "Efficient Substructure Searching of Large Chemical Libraries: The ABCD Chemical Cartridge," J. Chem. Inf. Model., 2011. doi: 10.1021/ci200413e
  2. Barnard J. M., "Substructure searching methods: Old and new," J. Chemical Information and Computer Sciences, vol. 33, no. 4, pp. 532-538, 1993. doi: 10.1021/ci00014a001
  3. Cordella L. P., Foggia P., Sansone C., and Vento M., "A (sub)graph isomorphism algorithm for matching large graphs." IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-72, Oct. 2004. doi: 10.1109/TPAMI.2004.75
  4. Ehrig H., Engels G., Kreowski H. -J., Rozenberg G., and Montanari U., Eds., Handbook of graph grammars and computing by graph transformation (Vols. 1.-3.). World Scientific, 1997-1999.
  5. Everett M. G. and Borgatti S. P., "Regular equivalence: General theory," Journal of mathematical sociology, vol. 19, no. 1, pp. 29-52, 1994. doi: 10.1080/0022250X.1994.9990134
  6. Fomin F. V. and Kratsch D., Exact Exponential Algorithms. Springer, 2011.
  7. Fuurst L., Mernik M., and Mahniˇc V., "Improving the graph grammar parser of Rekers and Sch¨urr," IET Software, vol. 5, no. 2, pp. 246-261, 2011. doi: 10.1049/iet-sen.2010.0081
  8. Hopkins B., "Kevin Bacon and graph theory," PRIMUS, vol. 14, no. 1, pp. 5-11, 2004. doi: 10.1080/10511970408984072
  9. Jackson M. O., Social and Economic Networks. Princeton, NJ, USA: Princeton University Press, 2008. ISBN 0691134405, 9780691134406
  10. Knoke D., Political Networks: The Structural Perspective, ser. Structural Analysis in the Social Sciences. Cambridge University Press, 1994. ISBN 9780521477628
  11. Liberti L., "Automatic generation of symmetry-breaking constraints," in COCOA, ser. Lecture Notes in Computer Science, B. Yang, D.-Z. Du, and C. Wang, Eds., vol. 5165. Springer, 2008. doi: 10.1007/978-3-540-85097-7 31 pp. 328-338.
  12. McKay B. D. and Piperno A., "Practical graph isomorphism, ii," J. Symbolic Computation, vol. 60, pp. 94-112, 2013. doi: 10.1016/j.jsc.2013.09.003
  13. Mucherino A., Lavor C., and Liberti L., "Exploiting symmetry properties of the discretizable molecular distance geometry problem," J. Bioinformatics and Computational Biology, vol. 10, no. 3, 2012. doi: 10.1142/S0219720012420097
  14. Rekers J. and Schurr A., "Defining and parsing visual languages with Layered Graph Grammars," Journal of Visual Languages and Computing, vol. 8, no. 1, pp. 27-55, 1997. doi: 10.1006/jvlc.1996.0027
  15. Rozenberg G. and Welzl E., "Boundary NLC graph grammars - basic definitions, normal forms, and complexity," Information and Control, vol. 69, no. 1-3, pp. 136-167, 1986. doi: 10.1016/S0019-9958(86)80045-6
  16. Ullmann J. R., "An Algorithm for Subgraph Isomorphism," J. Assoc. for Computing Machinery, vol. 23, pp. 31-42, 1976. doi: 10.1145/321921.321925
Cited by
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu