Authors:
Baumbach, Jan^{6} ; Ibragimov, R.^{4} ; Guo, Jian-Ying^{5}
Editor:
Frank Dehne, Roberto Solis-Oba, Jörg-Rüdiger Sack
Affiliations:
^{1} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{2} Computer Science, Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU^{3} University Library of Southern Denmark, SDU^{4} Max Planck Institute für Informatik^{5} Plantepatologi og Entomologi^{6} Department of Mathematics and Computer Science (IMADA), Faculty of Science, SDU
DOI:
10.1007/978-3-642-40104-6_37
Abstract:
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. © 2013 Springer-Verlag.
ISBN:
9783642401039
Type:
Book chapter
Language:
English
Published in:
Lecture Notes in Computer Science: 13th International Symposium, Wads 2013, 2013, p. 427-438
Main Research Area:
Science/technology
Publication Status:
Published
Series:
Lecture Notes in Computer Science
Review type:
Peer Review
Conference:
Algorithms & Data Structures Symposium, 2013
Publisher:
Springer
Submission year:
2013
Scientific Level:
Scientific
ID:
2185996313
Copyright ©
1998–2016.