A New Algorithm for the Hypergraph Transversal Problem
We consider the problem of finding all minimal transversals of a hypergraph H (∪) 2V, given by an explicit list of its hyperedges. We give a new decomposition technique for solving the problem with the following advantages: (i) Global parallelism: for certain classes of hyper-graphs, e.g. hypergraphs of bounded edge size, and any given integer k, the algorithm outputs k minimal transversals of H in time bounded by polylog(|V|,|W|,k) assuming poly(|V|, |H|, k) number of processors. Except for the case of graphs, none of the previously known algorithms for solving the same problem exhibit this feature. (ii)Using this technique, we also obtain new results on the complexity of generating minimal transversals for new classes of hypergraphs, namely hypergraphs of bounded dual-conformality, and hypergraphs in which every edge intersects every minimal transversal in a bounded number of vertices.
Leonid Khachiyan Endre Boros Khaled Elbassioni Vladimir Gurvich
Department of Computer Science, Rutgers University 110 Frelinghuysen Road, Piscataway NJ 08854-8003 RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway NJ 08854-8003 Max-Planck-Institut fur Informatik, Saarbriicken, Germany
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
767-776
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）