On the chain pair simplification problem

Chenglin Fan, Omrit Filtser, Matthew J. Katz, Tim Wylie, Binhai Zhu

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


The problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones in 3D has led Bereg et al. [4] to pose the Chain Pair Simplification problem (CPS). In this problem, given two polygonal chains A and B of lengths m and n, respectively, one needs to simplify them simultaneously, such that each of the resulting simplified chains, Aʹ and Bʹ, is of length at most k and the discrete Fréchet distance between Aʹ and Bʹ is at most δ, where k and δ are given parameters. In this paper we study the complexity of CPS under the discrete Fréchet distance (CPS-3F), i.e., where the quality of the simplifications is also measured by the discrete Fréchet distance. Since CPS-3F was posed in 2008, its complexity has remained open. In this paper, we prove that CPS-3F is actually polynomially solvable, by presenting an O(m2n2 min{m, n}) time algorithm for the corresponding minimization problem. On the other hand, we prove that if the vertices of the chains have integral weights then the problem is weakly NP-complete.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings
المحررونFrank Dehne, Jorg-Rudiger Sack, Ulrike Stege
ناشرSpringer Verlag
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)9783319218397
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2015
منشور خارجيًانعم
الحدث14th International Symposium on Algorithms and Data Structures, WADS 2015 - Victoria, كندا
المدة: ٥ أغسطس ٢٠١٥٧ أغسطس ٢٠١٥

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت9214
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference14th International Symposium on Algorithms and Data Structures, WADS 2015

ملاحظة ببليوغرافية

Publisher Copyright:
© Springer International Publishing Switzerland 2015.


أدرس بدقة موضوعات البحث “On the chain pair simplification problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا