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 worst-case time for a domino-free graph with edges and 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 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 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.

On computing the Galois lattice of Bipartite Distance Hereditary graphs / Apollonio, Nicola; Franciosa, Paolo Giulio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 226:(2017), pp. 1-9. [10.1016/j.dam.2017.04.004]

On computing the Galois lattice of Bipartite Distance Hereditary graphs

Nicola Apollonio
;
Paolo Giulio Franciosa
2017

Abstract

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 worst-case time for a domino-free graph with edges and 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 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 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.
2017
bipartite graphs;distance hereditary graphs; maximal bicliques; Galois lattices
01 Pubblicazione su rivista::01a Articolo in rivista
On computing the Galois lattice of Bipartite Distance Hereditary graphs / Apollonio, Nicola; Franciosa, Paolo Giulio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 226:(2017), pp. 1-9. [10.1016/j.dam.2017.04.004]
File allegati a questo prodotto
File Dimensione Formato  
Apollonio_Computing-Galois_2017.pdf

solo gestori archivio

Note: https://ac.els-cdn.com/S0166218X17301592/1-s2.0-S0166218X17301592-main.pdf?_tid=e946e174-e44a-4e40-83f8-e0d9b3ea1545&acdnat=1541515056_e040e2848d4cf07fe29bb2586ad86641
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 815.66 kB
Formato Adobe PDF
815.66 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1018217
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact