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: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2007
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06274caa a22007577a 4500 | ||
|---|---|---|---|
| 001 | PAPER-6535 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203613.0 | ||
| 008 | 190411s2007 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-34247167209 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a IFPLA | ||
| 100 | 1 | |a Lin, M.C. | |
| 245 | 1 | 0 | |a Faster recognition of clique-Helly and hereditary clique-Helly graphs |
| 260 | |c 2007 | ||
| 270 | 1 | 0 | |m Szwarcfiter, J.L.; Universidade Federal do Rio de Janeiro, Instituto de Matemática, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil; email: jayme@nce.ufrj.br |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Bandelt, H.J., Pesch, E., Dismantling absolute retracts of reflexive graphs (1989) European Journal Combinatorics, 10, pp. 211-220 | ||
| 504 | |a Bandelt, H.J., Prisner, E., Clique graphs and Helly graphs (1991) Journal of Combinatorial Theory B, 51, pp. 34-45 | ||
| 504 | |a Berge, C., (1970) Graphes et Hypergraphes, , Dunod, Paris | ||
| 504 | |a Bondy, A., Durán, G., Lin, M., Szwarcfiter, J.L., Self-clique graphs and matrix permutations (2003) Journal of Graph Theory, 44, pp. 178-192 | ||
| 504 | |a Bonomo, F., Chudnowsky, M., Durán, G., Partial characterizations of clique-perfect graphs (2005) Electronic Notes in Discrete Mathematics, 19, pp. 95-101 | ||
| 504 | |a Brandstädt, A., Le, V., Spinrad, J., Graph Classes: A Survey (1999) SIAM Monographs on Discrete Mathematics and Applications, , SIAM Publications, Philadelphia | ||
| 504 | |a Bretto, A., Ubéda, S., Zerovnik, J., A polynomial algorithm for the strong Helly property (2002) Information Processing Letters, 81, pp. 55-57 | ||
| 504 | |a Escalante, F., Über iterierte Clique-Graphen (1973) Abhandlungen des Mathematischen Seminars der Universität Hamburg, 39, pp. 59-68 | ||
| 504 | |a Hamelink, B.C., A partial characterization of clique graphs (1968) Journal of Combinatorial Theory, 5, pp. 192-197 | ||
| 504 | |a Larrión, F., Neumann-Lara, V., Pizaña, M.A., Porter, T.D., A hierarchy of self-clique graphs (2004) Discrete Mathematics, 282, pp. 193-208 | ||
| 504 | |a Nowakowski, R., Winkler, P., Vertex to vertex pursuit of a graph (1983) Discrete Mathematics, 43, pp. 235-239 | ||
| 504 | |a Prisner, E., Hereditary clique-Helly graphs (1993) Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220 | ||
| 504 | |a Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) Journal of Combinatorial Theory B, 10, pp. 102-108 | ||
| 504 | |a Szwarcfiter, J.L., Recognizing clique-Helly graphs (1997) Ars Combinatoria, 45, pp. 29-32 | ||
| 504 | |a Wallis, W.D., Zhang, G.H., On clique-irreducible graphs (1990) Journal of Combinatorial Mathematics and Combinatorial Computing, 8, pp. 187-193 | ||
| 520 | 3 | |a 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. |l eng | |
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq | ||
| 536 | |a Detalles de la financiación: Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, X212, X184 | ||
| 536 | |a Detalles de la financiación: Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro | ||
| 536 | |a Detalles de la financiación: * Corresponding author. E-mail addresses: oscarlin@dc.uba.ar (M.C. Lin), jayme@nce.ufrj.br (J.L. Szwarcfiter). 1 Partially supported by UBACyT Grants X184 and X212, CNPq under PROSUL project Proc. 490333/2004-4. 2 Partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq, and Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro, FAPERJ, Brazil. | ||
| 593 | |a Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina | ||
| 593 | |a Universidade Federal do Rio de Janeiro, Instituto de Matemática, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil | ||
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a CLIQUE-HELLY GRAPHS |
| 690 | 1 | 0 | |a DISK-HELLY GRAPHS |
| 690 | 1 | 0 | |a HELLY PROPERTY |
| 690 | 1 | 0 | |a HEREDITARY CLIQUE-HELLY GRAPHS |
| 690 | 1 | 0 | |a HEREDITARY DISK-HELLY GRAPHS |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a COMPUTATIONAL METHODS |
| 690 | 1 | 0 | |a SET THEORY |
| 690 | 1 | 0 | |a CLIQUE-HELLY GRAPHS |
| 690 | 1 | 0 | |a DISK-HELLY GRAPHS |
| 690 | 1 | 0 | |a HELLY PROPERTY |
| 690 | 1 | 0 | |a HEREDITARY CLIQUE HELLY GRAPHS |
| 690 | 1 | 0 | |a HEREDITARY DISK HELLY GRAPHS |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Szwarcfiter, J.L. | |
| 773 | 0 | |d 2007 |g v. 103 |h pp. 40-43 |k n. 1 |p Inf. Process. Lett. |x 00200190 |w (AR-BaUEN)CENRE-1599 |t Information Processing Letters | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-34247167209&doi=10.1016%2fj.ipl.2007.02.017&partnerID=40&md5=c613006218fb9dfe63589da4af883488 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.ipl.2007.02.017 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00200190_v103_n1_p40_Lin |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v103_n1_p40_Lin |y Registro en la Biblioteca Digital |
| 961 | |a paper_00200190_v103_n1_p40_Lin |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 67488 | ||