کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949607 | 1440197 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On computing the Galois lattice of bipartite distance hereditary graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The class of Bipartite Distance Hereditary (BDH) graphs is the intersection between bipartite domino-free and chordal bipartite graphs. Graphs in both the latter classes have linearly many maximal bicliques, implying the existence of polynomial-time algorithms for computing the associated Galois lattice. Such a lattice can indeed be built in O(mâ
n)worst-case time for a domino-free graph with m edges and n vertices. In Apollonio et al. (2015), BDH graphs have been characterized as those bipartite graphs whose Galois lattice is tree-like. In this paper we give a sharp upper bound on the number of maximal bicliques of a BDH graph and we provide an O(m) time-worst-case algorithm for incrementally computing its Galois lattice. The algorithm in turn implies a constructive proof of the if part of the characterization above. Moreover, we give an O(n) worst-case space and time encoding of both the input graph and its Galois lattice, provided that the reverse of a Bandelt and Mulder building sequence is given.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 1-9
Journal: Discrete Applied Mathematics - Volume 226, 31 July 2017, Pages 1-9
نویسندگان
Nicola Apollonio, Paolo Giulio Franciosa,