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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
PCGsurvey.pdf
Solo gestori archivio
Tipologia:
Versione dell'editore
Licenza:
DRM (Digital rights management) non definiti
Dimensione
389.64 kB
Formato
Adobe PDF
|
389.64 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
