Title :
Matching Matchings
Author :
Bacso, Gabor ; Keszler, Anita ; Tuza, Zsolt
Abstract :
This paper presents the first steps toward a graph comparison method based on matching matchings, or in other words, comparison of independent edge sets in graphs. The novelty of our approach is to use matchings for calculating distance of graphs in case of edge-colored graphs. This idea can be used as a preprocessing step of graph querying applications, to speed up exact and inexact graph matching methods. We introduce the notion of colored matchings and prove some properties of them in edge colored complete graphs and complete bipartite graphs in case of two colors.
Keywords :
graph theory; pattern matching; query processing; complete bipartite graphs; edge colored complete graphs; exact graph matching method; graph comparison method; graph querying applications; inexact graph matching methods; matching matchings; Bipartite graph; Color; Computational modeling; Image color analysis; Pattern matching; Polynomials; colored matching; edge-colored graph; inexact graph matching;
Conference_Titel :
Engineering of Computer Based Systems (ECBS-EERC), 2013 3rd Eastern European Regional Conference on the
Conference_Location :
Budapest
DOI :
10.1109/ECBS-EERC.2013.19
