Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 2

Proceedings of the 2014 Federated Conference on Computer Science and Information Systems

Exploratory Equivalence in Graphs: Definition and Algorithms

Jurij Mihelič, Luka Fürst, Uroš Čibej

DOI: http://dx.doi.org/10.15439/2014F352

Citation: Proceedings of the 2014 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 2, pages 447–456 (2014)

Full text

Abstract. 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.