Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Hypertree Decompositions: A Survey

Georg GottlobContact Information, Nicola LeoneContact Information and Francesco ScarcelloContact Information

(6)  Information Systems Institute, TU-Wien, Vienna, Austria
(7)  Dept. of Mathematics, Univ. of Calabria, Rende, CS, Italy
(8)  D.E.I.S., Univ. of Calabria, Rende, CS, Italy
Abstract
This paper surveys recent results related to the concept of hypertree decomposition and the associated notion of hypertree width. A hypertree decomposition of a hypergraph (similar to a tree decomposition of a graph) is a suitable clustering of its hyperedges yielding a tree or a forest. Important NP hard problems become tractable if restricted to instances whose associated hypergraphs are of bounded hypertree width. We also review a number of complexity results on problems whose structure is described by acyclic or nearly acyclic hypergraphs.

Contact Information Georg Gottlob
Email: gottlob@acm.org

Contact Information Nicola Leone
Email: leone@unical.it

Contact Information Francesco Scarcello
Email: scarcello@acm.org
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)