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.
On pairwise compatibility graphs: a survey / Calamoneri, Tiziana; B., Sinaimeri. - In: SIAM REVIEW. - ISSN 0036-1445. - STAMPA. - 58:3(2016), pp. 445-460. [10.1137/140978053]
On pairwise compatibility graphs: a survey
CALAMONERI, Tiziana;
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
Calamoneri_Pairwise_2016.pdf
solo utenti autorizzati
Note: versione dell'editore
Tipologia:
Altro materiale allegato
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
389.64 kB
Formato
Adobe PDF
|
389.64 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
