کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414539 | 680974 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of simplicial homology and independence complexes of chordal graphs
ترجمه فارسی عنوان
پیچیدگی مجتمع های سادکی همسانی و مستقلگراف های وتری
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی؛ همسانی ؛ مجتمع Clique ؛ مجتمع مستقل؛ نمودار Chordal
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove the NP-hardness of computing homology groups of simplicial complexes when the size of the input complex is measured by the number of maximal faces or the number of minimal non-faces. The latter case implies NP-hardness of the homology problem for clique and independence complexes of graphs.Our approach is based on the observation that the homology of an independence complex of a chordal graph can be described using what we call strong induced matchings in the graph (also known as cross-cycles). We show that finding such a matching of a specified size in a chordal graph is NP-hard.We further study the computational complexity of finding any cross-cycle in arbitrary and chordal graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 57, August 2016, Pages 8–18
Journal: Computational Geometry - Volume 57, August 2016, Pages 8–18
نویسندگان
Michał Adamaszek, Juraj Stacho,