TY - GEN

T1 - Compactness-preserving mapping on trees

AU - Baumbach, Jan

AU - Guo, Jiong

AU - Ibragimov, Rashid

N1 - Funding Information:
Supported by the DFG Excellence Cluster MMCI and the International Max Planck Research School.

PY - 2014

Y1 - 2014

N2 - We introduce a generalization of the graph isomorphism problem. Given two graphs G 1=(V 1, E 1) and G 2=(V 2, E 2) and two integers l and d, we seek for a one-to-one mapping f:V 1→V 2, such that for every v ∈ V 1, it holds that Lv -Lv d, where,Lv ∑ u∈N1G1 dist G1 (V,U), L v:= ∑ u∈N1G1 (V) dist G2 (f(v), f(u)), and Ni G (v) denotes the set of vertices which have distance at most i to v in a graph G. We call this problem Compactness-Preserving Mapping (CPM). In the paper we study CPM with input graphs being trees and present a dichotomy of classical complexity with respect to different values of l and d. CPM on trees can be solved in polynomial time only if l ≤2 and d≤1.

AB - We introduce a generalization of the graph isomorphism problem. Given two graphs G 1=(V 1, E 1) and G 2=(V 2, E 2) and two integers l and d, we seek for a one-to-one mapping f:V 1→V 2, such that for every v ∈ V 1, it holds that Lv -Lv d, where,Lv ∑ u∈N1G1 dist G1 (V,U), L v:= ∑ u∈N1G1 (V) dist G2 (f(v), f(u)), and Ni G (v) denotes the set of vertices which have distance at most i to v in a graph G. We call this problem Compactness-Preserving Mapping (CPM). In the paper we study CPM with input graphs being trees and present a dichotomy of classical complexity with respect to different values of l and d. CPM on trees can be solved in polynomial time only if l ≤2 and d≤1.

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

U2 - 10.1007/978-3-319-07566-2_17

DO - 10.1007/978-3-319-07566-2_17

M3 - Conference contribution

AN - SCOPUS:84958520721

SN - 9783319075655

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 162

EP - 171

BT - Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings

PB - Springer Verlag

T2 - 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014

Y2 - 16 June 2014 through 18 June 2014

ER -