PUMA publications for /author/Georg%20Gottlobhttps://puma.uni-kassel.de/author/Georg%20GottlobPUMA RSS feed for /author/Georg%20Gottlob2024-03-28T17:52:38+01:00Identifying the Minimal Transversals of a Hypergraph and Related Problemshttps://puma.uni-kassel.de/bibtex/2cd05f6dae9a4feed33fa7df223ab89ec/folkefolke2010-05-04T08:55:46+02:00conp theory hypergraph complexity <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Thomas Eiter" itemprop="url" href="/author/Thomas%20Eiter"><span itemprop="name">T. Eiter</span></a></span>, and <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Georg Gottlob" itemprop="url" href="/author/Georg%20Gottlob"><span itemprop="name">G. Gottlob</span></a></span>. </span><span itemtype="http://schema.org/PublicationIssue" itemscope="itemscope" itemprop="isPartOf"><span itemtype="http://schema.org/Periodical" itemscope="itemscope" itemprop="isPartOf"><span itemprop="name"><em>SIAM J. Comput.</em></span></span> <em><span itemtype="http://schema.org/PublicationVolume" itemscope="itemscope" itemprop="isPartOf"><span itemprop="volumeNumber">24 </span></span>(<span itemprop="issueNumber">6</span>):
<span itemprop="pagination">1278--1304</span></em> </span>(<em><span>1995<meta content="1995" itemprop="datePublished"/></span></em>)Tue May 04 08:55:46 CEST 2010Philadelphia, PA, USASIAM J. Comput.61278--1304Identifying the Minimal Transversals of a Hypergraph and Related Problems241995conp theory hypergraph complexity The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $\cal H$, decide if every subset of vertices is contained in or contains some edge of $\cal H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs ${\cal H}_{1}, {\cal H}_{2}$, decide if the sets in ${\cal H}_{2}$ are all the minimal transversals of ${\cal H}_{1}$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.The Lixto Data Extraction Project - Back and Forth between Theory and Practicehttps://puma.uni-kassel.de/bibtex/21cc97508ecfcb6c56e201df3065e708b/hothohotho2005-12-20T20:21:42+01:00practice project theory back lixto data extraction <span class="authorEditorList"><span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Georg Gottlob" itemprop="url" href="/author/Georg%20Gottlob"><span itemprop="name">G. Gottlob</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Christoph Koch" itemprop="url" href="/author/Christoph%20Koch"><span itemprop="name">C. Koch</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Robert Baumgartner" itemprop="url" href="/author/Robert%20Baumgartner"><span itemprop="name">R. Baumgartner</span></a></span>, <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Marcus Herzog" itemprop="url" href="/author/Marcus%20Herzog"><span itemprop="name">M. Herzog</span></a></span>, and <span itemtype="http://schema.org/Person" itemscope="itemscope" itemprop="author"><a title="Sergio Flesca" itemprop="url" href="/author/Sergio%20Flesca"><span itemprop="name">S. Flesca</span></a></span>. </span><span itemtype="http://schema.org/Book" itemscope="itemscope" itemprop="isPartOf"><em><span itemprop="name">Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 14-16, 2004, Paris, France</span>, </em></span><em>page <span itemprop="pagination">1-12</span>. </em><em><span itemprop="publisher">ACM</span>, </em>(<em><span>2004<meta content="2004" itemprop="datePublished"/></span></em>)Tue Dec 20 20:21:42 CET 2005Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, June 14-16, 2004, Paris, France1-12The Lixto Data Extraction Project - Back and Forth between Theory and Practice2004practice project theory back lixto data extraction