On computing the Galois Lattice of Bipartite Distance Hereditary graphs
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)O(m?n)worst-case time for a domino-free graph with mm edges and nn vertices. In Apollonio et al. (2015), BDH graphs have been characterized as those bipartite graphs whose Galois lattice is tree-like.






