Name
Title | ||
|---|---|---|
Polynomial recognition of equal unions in hypergraphs with few vertices of large degree |
Abstract | ||
|---|---|---|
A family of nonempty sets has the equal union property if there exist two nonempty disjoint subfamilies having equal unions. If every point belongs to the unions, then we say the family has the full equal union property. Recognition of both properties is NP-complete even when restricted to families for which the degree of every point is at most three. In this paper we show that both recognition problems can be solved in polynomial time for families in which there is a bound on the number of points whose degree exceeds two. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.jda.2005.03.001 | J. Discrete Algorithms |
Keywords | Field | DocType |
polynomial time,nonempty disjoint,hypergraphs,equal union property,polynomial recognition,full equal union property,large degree,l -matrices,recognition problem,turing reduction,nonempty set,equal union | Discrete mathematics,Combinatorics,Disjoint sets,Polynomial,Vertex (geometry),Constraint graph,Turing reduction,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
4 | 2 | Journal of Discrete Algorithms |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Pokrass Jacobs | 1 | 269 | 34.30 |
| Robert E. Jamison | 2 | 395 | 84.11 |