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 -