CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishEdge-Path-Tree graphs are intersection graphs of Edge-Path-Tree matrices that is matrices whose columns are incidence vectors of edge-sets of paths in a given tree. Edge-Path-Tree graphs have polynomially many cliques as proved in [4] and [7]. Therefore, the problem of finding a clique of maximum weight in these graphs is solvable in strongly polynomial time. In this paper we extend this result to a proper superclass of Edge-Path-Tree graphs. Each graph in the class is defined as the intersection graph of a matrix with no submatrix in a set W of seven small forbidden submatrices. By forbidding an eighth small matrix, our result specializes to Edge-Path-Tree graphs
Caramia, M., & Apollonio, N. (2009). A Superclass of Edge-Path-Tree graphs with few cliques.
| Tipologia: | Altro |
| Citazione: | Caramia, M., & Apollonio, N. (2009). A Superclass of Edge-Path-Tree graphs with few cliques. |
| Lingua: | en |
| Data di pubblicazione: | 27-feb-2009 |
| Titolo: | A Superclass of Edge-Path-Tree graphs with few cliques |
| Autori: | Caramia, Massimiliano;Apollonio, Nicola |
| Autori: | |
| Appare nelle tipologie: | 99 - Altro |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| RR04.09_Apollonio_Caramia.pdf | N/A | Open Access Visualizza/Apri |
Copyright © 2021