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
Autores principales: Lin, M.C., Szwarcfiter, J.L.
Formato: JOUR
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: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 todo:paper_00200190_v103_n1_p40_Lin
record_format dspace
spelling todo:paper_00200190_v103_n1_p40_Lin2023-10-03T14:16:37Z Faster recognition of clique-Helly and hereditary clique-Helly graphs Lin, M.C. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.C.
Szwarcfiter, J.L.
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.
format JOUR
author Lin, M.C.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Szwarcfiter, J.L.
author_sort Lin, M.C.
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
url http://hdl.handle.net/20.500.12110/paper_00200190_v103_n1_p40_Lin
work_keys_str_mv AT linmc fasterrecognitionofcliquehellyandhereditarycliquehellygraphs
AT szwarcfiterjl fasterrecognitionofcliquehellyandhereditarycliquehellygraphs
_version_ 1782025157242519552

Ejemplares similares