Edge-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  and . 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.
|Citazione:||Caramia, M., & Apollonio, N. (2009). A Superclass of Edge-Path-Tree graphs with few cliques.|
|Data di pubblicazione:||27-feb-2009|
|Titolo:||A Superclass of Edge-Path-Tree graphs with few cliques|
|Autori:||Caramia, Massimiliano;Apollonio, Nicola|
|Appare nelle tipologie:||99 - Altro|