Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Characterization and Recognition of Generalized Clique-Helly Graphs
verfasst von : Mitre Costa Dourado, Fábio Protti, Jayme Luiz Szwarcfiter
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
p
≥ 1 and
q
≥ 0 be integers. A family of sets
${\mathcal F}$
is
(p
,q
)-intersecting
when every subfamily
${\mathcal F}' \subseteq {\mathcal F}$
formed by
p
or less members has total intersection of cardinality at least
q
. A family of sets
${\mathcal F}$
is
(p
,q
)-Helly
when every (
p
,
q
)-intersecting subfamily
${\mathcal F}' \subseteq {\mathcal F}$
has total intersection of cardinality at least
q
. A graph
G
is a
(p
,q
)-clique-Helly graph
when its family of (maximal) cliques is (
p
,
q
)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case
p
=2,
q
=1. In this work we present a characterization for (
p
,
q
)-clique-Helly graphs. For fixed
p
,
q
, this characterization leads to a polynomial-time recognition algorithm. When
p
or
q
is not fixed, it is shown that the recognition of (
p
,
q
)-clique-Helly graphs is NP-hard.