On the strong \(p\)-Helly property (Q2482102): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q4088860 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A polynomial algorithm for the strong Helly property / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Induced matchings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph-Theoretic Concepts in Computer Science / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity aspects of generalized Helly hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The edge intersection graphs of paths in a tree / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On cliques in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4288086 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4842710 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3980562 / rank | |||
Normal rank |
Latest revision as of 21:33, 27 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the strong \(p\)-Helly property |
scientific article |
Statements
On the strong \(p\)-Helly property (English)
0 references
16 April 2008
0 references
The hypergraph \(\mathcal H\) is called \textit{\((p,q)\)-intersecting} if any \(p\) edges have at least \(q\) common points. It is \textit{\((p,q,s)\)-Helly} if every \((p,q)\)-intersecting partial hypergraph of it has an \(s\)-core. (That is if a subset \(\mathcal E\) of the edges of \(\mathcal H\) is \((p,q)\)-intersecting, then there are \(s\) points in common in the edges of \(\mathcal E\). The particular case \((2,1,1)\)-Helly coincides with the usual notion of Helly hypergraphs.) Finally the hypergraph is \textit{strong \(p\)-Helly} if for every edge-subset \(\mathcal E\) contains at most \(p\) edges s.t. their intersection coincides with the complete intersection of all edges in \(\mathcal E\). One of the main results of this nice paper is a structural characterization of strong \(p\)-Helly hypergraphs, which in turn provides an algorithm to recognize such hypergraphs. The algorithm has polynomial time-complexity for fixed \(p\)'s. In contrast the recognition problem is in \textit{co-NP} for arbitrary \(p.\) The paper also studies some closely related problems.
0 references
strong Helly-property
0 references
hereditary clique-Helly graphs
0 references
computationally complexity
0 references