A graph is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree where each leaf corresponds to a vertex of the graph, and an edge u,v exists in the graph if and only if the weight of the path connecting the leaves u and v in the tree falls within a specified interval. PCGs have been extensively studied, and numerous subclasses and generalizations have been introduced, expanding their applicability and theoretical interest. In this survey, we briefly review the existing results on these variants of PCGs and highlight several intriguing open problems, focusing on the main challenges and potential directions for future research.
Calamoneri, T.; Monti, A.; Sinaimeri, Blerina. (2025). On Variants of PCGs: A Survey of Current Results and Open Problems. In B. Goldengorin (ed.) (Eds.), Theory, Algorithms, and Experiments in Applied Optimization. In Honor of the 70th Birthday of Panos Pardalos (pp. 39-59). Springer. Isbn: 9783031913563. Isbn: 9783031913570. Doi: 10.1007/978-3-031-91357-0_3.
On Variants of PCGs: A Survey of Current Results and Open Problems
Sinaimeri B.
2025
Abstract
A graph is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree where each leaf corresponds to a vertex of the graph, and an edge u,v exists in the graph if and only if the weight of the path connecting the leaves u and v in the tree falls within a specified interval. PCGs have been extensively studied, and numerous subclasses and generalizations have been introduced, expanding their applicability and theoretical interest. In this survey, we briefly review the existing results on these variants of PCGs and highlight several intriguing open problems, focusing on the main challenges and potential directions for future research.
| File | Dimensione | Formato | |
|---|---|---|---|
|
generalisations_PCGs_review (14).pdf
Solo gestori archivio
Tipologia:
Documento in Pre-print
Licenza:
Tutti i diritti riservati
Dimensione
1.28 MB
Formato
Adobe PDF
|
1.28 MB | Adobe PDF | Visualizza/Apri |
|
978-3-031-91357-0_03.pdf
Solo gestori archivio
Tipologia:
Versione dell'editore
Licenza:
Tutti i diritti riservati
Dimensione
1.62 MB
Formato
Adobe PDF
|
1.62 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
