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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Lin, Min Chih
Publicado:	2007
Materias:	Algorithms Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique-Helly graphs Hereditary disk-Helly graphs Computational complexity Computational methods Set theory Hereditary clique Helly graphs Hereditary disk Helly graphs Graph theory
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:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00200190_v103_n1_p40_Lin
record_format	dspace
spelling	paper:paper_00200190_v103_n1_p40_Lin2023-06-08T14:40:19Z Faster recognition of clique-Helly and hereditary clique-Helly graphs Lin, Min Chih Algorithms Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique-Helly graphs Hereditary disk-Helly graphs Algorithms Computational complexity Computational methods Set theory Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique Helly graphs Hereditary disk Helly graphs Graph theory 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. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2007 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
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Algorithms Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique-Helly graphs Hereditary disk-Helly graphs Algorithms Computational complexity Computational methods Set theory Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique Helly graphs Hereditary disk Helly graphs Graph theory
spellingShingle	Algorithms Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique-Helly graphs Hereditary disk-Helly graphs Algorithms Computational complexity Computational methods Set theory Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique Helly graphs Hereditary disk Helly graphs Graph theory Lin, Min Chih Faster recognition of clique-Helly and hereditary clique-Helly graphs
topic_facet	Algorithms Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique-Helly graphs Hereditary disk-Helly graphs Algorithms Computational complexity Computational methods Set theory Clique-Helly graphs Disk-Helly graphs Helly property Hereditary clique Helly graphs Hereditary disk Helly graphs Graph theory
description	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.
author	Lin, Min Chih
author_facet	Lin, Min Chih
author_sort	Lin, Min Chih
title	Faster recognition of clique-Helly and hereditary clique-Helly graphs
title_short	Faster recognition of clique-Helly and hereditary clique-Helly graphs
title_full	Faster recognition of clique-Helly and hereditary clique-Helly graphs
title_fullStr	Faster recognition of clique-Helly and hereditary clique-Helly graphs
title_full_unstemmed	Faster recognition of clique-Helly and hereditary clique-Helly graphs
title_sort	faster recognition of clique-helly and hereditary clique-helly graphs
publishDate	2007
url	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
work_keys_str_mv	AT linminchih fasterrecognitionofcliquehellyandhereditarycliquehellygraphs
_version_	1768541829232328704

Faster recognition of clique-Helly and hereditary clique-Helly graphs

Ejemplares similares