TY - CHAP

T1 - Neighborhood-preserving mapping between trees

AU - Baumbach, Jan

AU - Ibragimov, R.

AU - Guo, Jian-Ying

PY - 2013/1/1

Y1 - 2013/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84881133899&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40104-6_37

DO - 10.1007/978-3-642-40104-6_37

M3 - Book chapter

AN - SCOPUS:84881133899

SN - 9783642401039

T3 - Lecture Notes in Computer Science

SP - 427

EP - 438

BT - Algorithms and Data Structures

A2 - Dehne, Frank

A2 - Solis-Oba, Roberto

A2 - Sack, Jörg-Rüdiger

PB - Springer

Y2 - 12 August 2013 through 14 August 2013

ER -