Name
Abstract | ||
|---|---|---|
A hypergraph H is set of vertices V together with a collection of nonempty subsets of it, called the hyperedges of H. A partial hypergraph of H is a hypergraph whose hyperedges are all hyperedges of H, whereas for V′⊆V the subhypergraph (induced by V′) is a hypergraph with vertices V′ and having as hyperedges the subsets obtained as nonempty intersections of V′ and each of the hyperedges of H. For p⩾1 say that H is p-intersecting when every subset formed by p hyperedges of H contain a common vertex. Say that H is p-Helly when every p-intersecting partial hypergraph H′ of H contains a vertex belonging to all the hyperedges of H′. A hypergraph is hereditary p-Helly when every (induced) subhypergraph of it is p-Helly. In this paper we describe new characterizations for hereditary p-Helly hypergraphs and discuss the recognition problems for both p-Helly and hereditary p-Helly hypergraphs. The proposed algorithms improve the complexity of the existing recognition algorithms. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.ipl.2008.05.013 | Information Processing Letters |
Keywords | DocType | Volume |
Algorithms,p-Helly hypergraphs,Hereditary p-Helly hypergraphs | Journal | 108 |
Issue | ISSN | Citations |
4 | 0020-0190 | 0 |
PageRank | References | Authors |
0.34 | 3 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Min Chih Lin | 2 | 259 | 21.22 |
| Fábio Protti | 3 | 357 | 46.14 |
| Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |