Neighborhood-preserving mapping between trees

Jan Baumbach, R. Ibragimov, Jian-Ying Guo

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review

Abstrakt

We introduce a variation of the graph isomorphism problem, where, given two graphs G = (V,E) and G = (V,E) and three integers l, d, and k, we seek for a set ⊆ V and a one-to-one mapping f:V → V such that |D| ≤ k and for every vertex v ∈ V \ D and every vertex u ∈ N (v) \ D we have f(u) ∈ N (f(v)). Here, for a graph G and a vertex v, we use N(v) to denote the set of vertices which have distance at most i to v in G. We call this problem Neighborhood-Preserving Mapping (NPM). The main result of this paper is a complete dichotomy of the classical complexity of NPM on trees with respect to different values of l,d,k. Additionally, we present two dynamic programming algorithms for the case that one of the input trees is a path.
OriginalsprogEngelsk
TitelAlgorithms and Data Structures : 13th International Symposium, WADS 2013
RedaktørerFrank Dehne, Roberto Solis-Oba, Jörg-Rüdiger Sack
Antal sider12
ForlagSpringer
Publikationsdato1. jan. 2013
Sider427-438
ISBN (Trykt)9783642401039
DOI
StatusUdgivet - 1. jan. 2013
BegivenhedAlgorithms & Data Structures Symposium - University of Western Ontario, London, Ontario, Canada
Varighed: 12. aug. 201314. aug. 2013

Konference

KonferenceAlgorithms & Data Structures Symposium
LokationUniversity of Western Ontario
Land/OmrådeCanada
ByLondon, Ontario
Periode12/08/201314/08/2013
NavnLecture Notes in Computer Science
Vol/bind8037
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'Neighborhood-preserving mapping between trees'. Sammen danner de et unikt fingeraftryk.

Citationsformater