Name
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(nm^2) and O(n^2m), respectively, for a graph with n vertices and m edges. In this Note, we describe algorithms which recognize both classes in O(m^2) time. These algorithms also reduce the complexity of recognizing some other classes, as disk-Helly graphs. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ipl.2007.02.017 | Inf. Process. Lett. |
Keywords | Field | DocType |
disk-helly graphs,as disk-helly graphs. keywords: algorithms,hereditary clique-helly,induced subgraph,best algorithm,disk-helly graph,hereditary clique-helly graphs,complexities o,m edge,faster recognition,hereditary disk-helly graphs.,graph g,helly prop- erty,pairwise intersecting subsets,common element,other classes,hereditary clique-helly graph,clique-helly graphs,algorithms | Discrete mathematics,Family of sets,Combinatorics,Vertex (geometry),Clique,Chordal graph,Clique-sum,Induced subgraph,Pathwidth,Clique (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
103 | 1 | 0020-0190 |
Citations | PageRank | References |
6 | 0.60 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Jayme L. Szwarcfiter | 2 | 546 | 45.97 |