[Back]


Contributions to Proceedings:

T. Eiter, G. Gottlob:
"Hypergraph Transversal Computation and Related Problems in Logic and AI";
in: "Logics in Artificial Intelligence, LNAI 2424", S. Flesca, S. Greco, N. Leone, G. Ianni (ed.); Springer, Cosenza, Italy, 2002, ISBN: 3-540-44190-5, 549 - 564.



English abstract:
Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science. In the present paper, we address this problem and its decisional variant, i.e., the recognition of the transversal hypergraph for another hypergraph. We survey some results on problems which are known to be related to computing the transversal hypergraph, where we focus on problems in propositional Logic and AI. Some of the results habe been established already some time ago, and were announced but their derivation was not widely disseminated. We then address recent developments on the computational complexity of computing resp. recognizing the transversal hypergraph. The precise complexity if these problems is not known to date, and is in fact open for more than 20 years now.

Created from the Publication Database of the Vienna University of Technology.