DocumentCode
643946
Title
Matching Matchings
Author
Bacso, Gabor ; Keszler, Anita ; Tuza, Zsolt
fYear
2013
fDate
29-30 Aug. 2013
Firstpage
85
Lastpage
94
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Engineering of Computer Based Systems (ECBS-EERC), 2013 3rd Eastern European Regional Conference on the
Conference_Location
Budapest
Type
conf
DOI
10.1109/ECBS-EERC.2013.19
Filename
6664514
Link To Document