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.
|
 |
Hypertree Decompositions: A Survey
| |
|
Hypertree Decompositions: A Survey
Georg Gottlob6 , Nicola Leone7 and Francesco Scarcello8 
| (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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|