License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07071.11
URN: urn:nbn:de:0030-drops-10716
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1071/
Go to the corresponding Portal

Fraikin, Catherine ; Van Dooren, Paul

Graph matching with type constraints on nodes and edges

pdf-format:
07071.VanDoorenPaul.Paper.1071.pdf (0.2 MB)

Abstract

In this paper, we consider two particular problems of directed
graph matching. The first problem concerns graphs with nodes that
have been subdivided into classes of different type. The second
problem treats graphs with edges of different types. In the two
cases, the matching process is based on a constrained projection
of the nodes and of the edges of both graphs in a lower
dimensional space. The procedures are formulated as non-convex
optimization problems. The objective functions use the adjacency
matrices and the constraints on the problem impose the isometry of
the so-called projections. Iterative algorithms are proposed to
solve the optimization problems. As illustration, we give an
example of graph matching for graphs with two types of nodes and
graphs with two types of edges.

BibTeX - Entry

@InProceedings{fraikin_et_al:DagSemProc.07071.11,
  author =	{Fraikin, Catherine and Van Dooren, Paul},
  title =	{{Graph matching with type constraints on nodes and edges}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1071},
  URN =		{urn:nbn:de:0030-drops-10716},
  doi =		{10.4230/DagSemProc.07071.11},
  annote =	{Keywords: Graph matching, Optimization, Typed nodes, Typed edges}
}

Keywords: Graph matching, Optimization, Typed nodes, Typed edges
Collection: 07071 - Web Information Retrieval and Linear Algebra Algorithms
Issue Date: 2007
Date of publication: 28.06.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI