Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 2 | 447--456
Tytuł artykułu

Exploratory Equivalence in Graphs: Definition and Algorithms

Warianty tytułu
Języki publikacji
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)
Opis fizyczny
  • University of Ljubljana, Slovenia
  • University of Ljubljana, Slovenia
  • University of Ljubljana, Slovenia
  • 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
  • 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
  • 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
  • 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.
  • 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
  • Fomin F. V. and Kratsch D., Exact Exponential Algorithms. Springer, 2011.
  • 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
  • Hopkins B., "Kevin Bacon and graph theory," PRIMUS, vol. 14, no. 1, pp. 5-11, 2004. doi: 10.1080/10511970408984072
  • Jackson M. O., Social and Economic Networks. Princeton, NJ, USA: Princeton University Press, 2008. ISBN 0691134405, 9780691134406
  • Knoke D., Political Networks: The Structural Perspective, ser. Structural Analysis in the Social Sciences. Cambridge University Press, 1994. ISBN 9780521477628
  • 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.
  • 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
  • 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
  • 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
  • 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
  • Ullmann J. R., "An Algorithm for Subgraph Isomorphism," J. Assoc. for Computing Machinery, vol. 23, pp. 31-42, 1976. doi: 10.1145/321921.321925
Typ dokumentu
Identyfikator YADDA

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.