Faster recognition of clique-Helly and hereditary clique-Helly graphs
A family of subsets of a set is Helly when every subfamily of it, which is formed by pairwise intersecting subsets contains a common element. A graph G is clique-Helly when the family of its (maximal) cliques is Helly, while G is hereditary clique-Helly when every induced subgraph of it is clique-He...
Guardado en:
| Autor principal: | |
|---|---|
| Publicado: |
2007
|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v103_n1_p40_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v103_n1_p40_Lin |
| Aporte de: |
| Sumario: | A family of subsets of a set is Helly when every subfamily of it, which is formed by pairwise intersecting subsets contains a common element. A graph G is clique-Helly when the family of its (maximal) cliques is Helly, while G is hereditary clique-Helly when every induced subgraph of it is clique-Helly. The best algorithms currently known to recognize clique-Helly and hereditary clique-Helly graphs have complexities O (n m2) and O (n2 m), respectively, for a graph with n vertices and m edges. In this Note, we describe algorithms which recognize both classes in O (m2) time. These algorithms also reduce the complexity of recognizing some other classes, as disk-Helly graphs. © 2007 Elsevier B.V. All rights reserved. |
|---|