DROPS

Document

Graph matching with type constraints on nodes and edges

Authors: Catherine Fraikin and Paul Van Dooren

Published in: Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007)

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.

Cite as

Catherine Fraikin and Paul Van Dooren. Graph matching with type constraints on nodes and edges. In Web Information Retrieval and Linear Algebra Algorithms. Dagstuhl Seminar Proceedings, Volume 7071, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07071.11},
  URN =		{urn:nbn:de:0030-drops-10716},
  doi =		{10.4230/DagSemProc.07071.11},
  annote =	{Keywords: Graph matching, Optimization, Typed nodes, Typed edges}
}

Search Results

Documents authored by Van Dooren, Paul

Graph matching with type constraints on nodes and edges

Abstract

Cite as

Thanks for your feedback!

Could not send message