Polynomial recognition of equal unions in hypergraphs with few vertices of large degree (Q2458923): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 00:13, 3 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Polynomial recognition of equal unions in hypergraphs with few vertices of large degree |
scientific article |
Statements
Polynomial recognition of equal unions in hypergraphs with few vertices of large degree (English)
0 references
5 November 2007
0 references
A system of nonempty subsets of a finite underlying set has the equal union property if there are two disjoint subfamilies with equal union. If the union covers the entire underlying set, then the system has the full equal union property. The recognition of both properties is NP-complete if the number of points with at least degree three is unbounded. However, as it is shown in this paper, the problems become polynomially solvable if there exists such a constant upper bound.
0 references
hypergraph
0 references
equal union property
0 references
\(L\)-matrices
0 references
polynomial time
0 references
Turing reduction
0 references
