Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428832 | Information Processing Letters | 2007 | 4 Pages |
Abstract
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(nm2) and O(n2m), 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics