Kernels for acyclic digraphs

C.H. Elzinga; H. Wang

doi:10.1016/j.patrec.2012.07.017

Kernels for acyclic digraphs

C.H. Elzinga
, H. Wang

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

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 language	English
Pages (from-to)	2239-2244
Number of pages	5
Journal	Pattern Recognition Letters
Volume	33
DOIs	https://doi.org/10.1016/j.patrec.2012.07.017
Publication status	Published - 2012

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Access to Document

10.1016/j.patrec.2012.07.017

Persistent URL (handle)

Persistent link

Cite this

@article{23b7314a45dc498088ab8514b0c3ed42,

title = "Kernels for acyclic digraphs",

abstract = "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. {\textcopyright} 2012 Elsevier B.V. All rights reserved.",

author = "C.H. Elzinga and H. Wang",

year = "2012",

doi = "10.1016/j.patrec.2012.07.017",

language = "English",

volume = "33",

pages = "2239--2244",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Kernels for acyclic digraphs

AU - Elzinga, C.H.

AU - Wang, H.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1016/j.patrec.2012.07.017

DO - 10.1016/j.patrec.2012.07.017

M3 - Article

SN - 0167-8655

VL - 33

SP - 2239

EP - 2244

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

ER -

Kernels for acyclic digraphs

Abstract

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this