Compactness-preserving mapping on trees

Jan Baumbach; Jiong Guo; Rashid Ibragimov

doi:10.1007/978-3-319-07566-2_17

Compactness-preserving mapping on trees

Jan Baumbach, Jiong Guo, Rashid Ibragimov

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We introduce a generalization of the graph isomorphism problem. Given two graphs G ₁=(V ₁, E ₁) and G ₂=(V ₂, E ₂) and two integers l and d, we seek for a one-to-one mapping f:V ₁→V ₂, such that for every v ∈ V ₁, it holds that L_v -L_v d, where,L_v ∑ u∈N¹G₁ dist G₁ (V,U), L _v:= ∑ u∈N¹G₁ (V) dist G₂ (f(v), f(u)), and Nⁱ _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 language	English
Title of host publication	Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings
Publisher	Springer Verlag
Pages	162-171
Number of pages	10
ISBN (Print)	9783319075655
DOIs	https://doi.org/10.1007/978-3-319-07566-2_17
State	Published - 2014
Externally published	Yes
Event	25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014 - Moscow, Russian Federation Duration: 16 Jun 2014 → 18 Jun 2014

Publication series

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

Conference

Conference	25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014
Country/Territory	Russian Federation
City	Moscow
Period	16/06/14 → 18/06/14

Access to Document

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

Cite this

Baumbach, J., Guo, J., & Ibragimov, R. (2014). Compactness-preserving mapping on trees. In Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings (pp. 162-171). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8486 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-07566-2_17

@inproceedings{260009d680a84ae7a22430e359f6e4e7,

title = "Compactness-preserving mapping on trees",

abstract = "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.",

author = "Jan Baumbach and Jiong Guo and Rashid Ibragimov",

note = "Funding Information: Supported by the DFG Excellence Cluster MMCI and the International Max Planck Research School.; 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014 ; Conference date: 16-06-2014 Through 18-06-2014",

year = "2014",

doi = "10.1007/978-3-319-07566-2_17",

language = "English",

isbn = "9783319075655",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "162--171",

booktitle = "Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings",

}

Baumbach, J, Guo, J & Ibragimov, R 2014, Compactness-preserving mapping on trees. in Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8486 LNCS, Springer Verlag, pp. 162-171, 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014, Moscow, Russian Federation, 16/06/14. https://doi.org/10.1007/978-3-319-07566-2_17

Compactness-preserving mapping on trees. / Baumbach, Jan; Guo, Jiong; Ibragimov, Rashid.
Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings. Springer Verlag, 2014. p. 162-171 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8486 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Compactness-preserving mapping on trees

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this