Compactness-preserving mapping on trees

Jan Baumbach, Jiong Guo, Rashid Ibragimov

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish
Title of host publicationCombinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings
PublisherSpringer Verlag
Number of pages10
ISBN (Print)9783319075655
StatePublished - 2014
Externally publishedYes
Event25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014 - Moscow, Russian Federation
Duration: 16 Jun 201418 Jun 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8486 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014
Country/TerritoryRussian Federation


Dive into the research topics of 'Compactness-preserving mapping on trees'. Together they form a unique fingerprint.

Cite this