A graph G = (V, E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two nonnegative real numbers dmin and dmax such that each leaf u of T is a node of V and there is an edge (u, v) ∈ E if and only if dmin ≤ dT (u, v) ≤ dmax, where dT (u, v) is the sum of weights of the edges on the unique path from u to v in T. In this article, we survey the state of the art concerning this class of graphs and some of its subclasses.

Pairwise compatibility graphs: A survey / Calamoneri, T.; Sinaimeri, Blerina. - In: SIAM REVIEW. - ISSN 0036-1445. - 58:3(2016), pp. 445-460. [10.1137/140978053]

Pairwise compatibility graphs: A survey

Sinaimeri B.
2016

Abstract

A graph G = (V, E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two nonnegative real numbers dmin and dmax such that each leaf u of T is a node of V and there is an edge (u, v) ∈ E if and only if dmin ≤ dT (u, v) ≤ dmax, where dT (u, v) is the sum of weights of the edges on the unique path from u to v in T. In this article, we survey the state of the art concerning this class of graphs and some of its subclasses.
Leaf power graphs; Min leaf power graphs; Pairwise compatibility graphs
Pairwise compatibility graphs: A survey / Calamoneri, T.; Sinaimeri, Blerina. - In: SIAM REVIEW. - ISSN 0036-1445. - 58:3(2016), pp. 445-460. [10.1137/140978053]
File in questo prodotto:
File Dimensione Formato  
PCGsurvey.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM non definito
Dimensione 389.64 kB
Formato Adobe PDF
389.64 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/11385/202515
Citazioni
  • Scopus 26
  • ???jsp.display-item.citation.isi??? 21
social impact