کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777844 1633051 2017 35 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Allowing cycles in discrete Morse theory
ترجمه فارسی عنوان
اجازه دادن به چرخه در نظریه گسسته مورس
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات هندسه و توپولوژی
چکیده انگلیسی
Discrete gradient vector fields are combinatorial structures that can be used for accelerating the homology computation of CW complexes, such as simplicial or cubical complexes, by reducing their number of cells. Consequently, they provide a bound for the Betti numbers (the most basic homological information). A discrete gradient vector field can eventually reduce the complex to its minimal form, having as many cells of each dimension as its corresponding Betti number, but this is not guaranteed. Moreover, finding an optimal discrete gradient vector field is an NP-hard problem. We describe here a generalization, which we call Homological Discrete Vector Field (HDVF), which can overcome these limitations by allowing cycles under a certain algebraic condition. In this work we define the HDVF and its associated reduction, we study how to efficiently compute a HDVF, we establish the relation between the HDVF and other concepts in computational homology and we estimate the average complexity of its computation. We also introduce five basic operations for modifying a HDVF, which can also be applied to discrete gradient vector fields.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Topology and its Applications - Volume 228, 1 September 2017, Pages 1-35
نویسندگان
, , , ,