Pairwise Compatibility Graphs: A Survey

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 $d_{min}$ and $d_{max}$ such that each leaf $u$ of $T$ is a node of $V$ and there is an edge $(u,v) \in E$ if and only if $d_{min} \leq d_T (u, v) \leq d_{max}$, where $d_T (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.
Type de document :
Article dans une revue
SIAM Review, Society for Industrial and Applied Mathematics, 2016, 58 (3), pp.445 - 460. 〈10.1137/140978053〉
Liste complète des métadonnées

Littérature citée [54 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01388533
Contributeur : Marie-France Sagot <>
Soumis le : lundi 29 mai 2017 - 10:26:44
Dernière modification le : mardi 16 janvier 2018 - 16:10:51
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 10:30:10

Fichier

SurveyPCG.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Tiziana Calamoneri, Blerina Sinaimeri. Pairwise Compatibility Graphs: A Survey. SIAM Review, Society for Industrial and Applied Mathematics, 2016, 58 (3), pp.445 - 460. 〈10.1137/140978053〉. 〈hal-01388533〉

Partager

Métriques

Consultations de la notice

102

Téléchargements de fichiers

24