Name
Abstract | ||
|---|---|---|
It is NP-Hard to find a proper 2-coloring of a given 2-colorable (bipartite) hypergraph H. We consider algorithms that will color such a hypergraph using few colors in polynomial time. The results of the paper can be summarized as follows: Let n denote the number of vertices of H and m the number of edges, (i) For bipartite hypergraphs of dimension k there is a polynomial time algorithm which produces a proper coloring using min
{ O(n1 -</font
> 1/k ),O((m/n)\tfrac1k -</font
> 1 )}\{ O(n^{1 - 1/k} ),O((m/n)^{\tfrac{1}{{k - 1}}} )\}
colors, (ii) For 3-uniform bipartite hypergraphs, the bound is reduced to O(n
2/9). (iii) For a class of dense 3-uniform bipartite hypergraphs, we have a randomized algorithm which can color optimally. (iv) For a model of random bipartite hypergraphs with edge probability p dn
–2, d > O a sufficiently large constant, we can almost surely find a proper 2-coloring. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1007/3-540-61310-2_26 | IPCO |
Keywords | DocType | ISBN |
coloring bipartite hypergraphs,randomized algorithm,polynomial time | Conference | 3-540-61310-2 |
Citations | PageRank | References |
25 | 1.51 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hui Chen | 1 | 37 | 8.46 |
| Alan M. Frieze | 2 | 4837 | 787.00 |