Kernels for acyclic digraphs

C.H. Elzinga, H. Wang

Research output: Contribution to JournalArticleAcademicpeer-review


This paper proposes two efficient kernels for comparing acyclic, directed graphs. The first kernel counts the number of common paths and allows for weighing according to path-length and/or according to the vertices contained in each particular path. The second kernel counts the number of paths in common minors of the graphs involved and allows for length- and vertex-weighting too. Both kernels have algorithmic complexity that is cubic in the size of the vertex-set. The performance of the algorithms is concisely demonstrated using synthetic and real data. © 2012 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)2239-2244
Number of pages5
JournalPattern Recognition Letters
Publication statusPublished - 2012


Dive into the research topics of 'Kernels for acyclic digraphs'. Together they form a unique fingerprint.

Cite this