|
|
|
Hypertree Complementary
Approaches to Constraint Satisfaction |
|
We considered the development of initial algorithms for hypertree decompositions.
We investigated hypertree-decomposition
methods that operate directly on the hypergraph. In
particular, at first we investigated algorithms for finding separator
candidates, i.e., sets of hyperedges that divide a
given hypergraph in such a way that a hypertree-decomposition of small width can be expected. Afterwards,
we investigated measures for evaluating separators in order to select the
best separator amongst the separator candidates. By recursively choosing such
separators for each partition, we obtain a hypertree-decomposition
of the given hypergraph. The better the separators
are chosen, the smaller the resultig hypertee-width
becomes. Our experience has shown that both problems (selecting separator
candidates and evaluating separators) are combinatorial highly expensive and
are only feasible when restricting the search space by the use of heuristics.
First experimental results, however, have shown that such a direct approach
leads only for small hypergraphs to good results. The
results of this research were presented in Workshop on Graph and Hypergraph Decompositions-Methods and Applications in
Computer Science (December 16-18, 2004, We started to collect benchmark examples from the literature and also
considered generating hypergraphs based on their
theoretical properties. We performed research on how to apply hypertree
decomposition in the context of data exchange. We designed and implemented the basic data structures for an efficient
implementation and evaluating hypertree-decomposition
approaches which will be developed in future. Our implementation-framework is
written in ANSI C++ and provides a series of useful subroutines that are
often used in hypertree-decomposition algorithms. Our group co-organized Workshop on Graph and Hypergraph
Decompositions-Methods and Applications in Computer Science (December 16-18,
2004, We performed research on Quantified Constraint
Satisfaction Problems and the use of structural decomposition methods to
simplify such problems. We extended our benchmark suite by further hypergraph examples. We completed our implementation-framework used as
basis for all our decomposition heuristics. We reimplemented McMahans heuristic based on bucket elimination and set
covering. We investigated the application of the famous
Eigenvector heuristic for hypertree decomposition. We investigated the application of branch
decomposition heuristics for hypertree
decomposition. We investigated hypertree
decomposition based on the dual hypergraph. We implemented all these approaches within our
implementation framework. We evaluated all these heuristics by our benchmark
examples. We automated experimental evaluations of implemented
algorithms for the benchmark examples.
We developed and implemented a new exact algorithm
for hypertree decomposition. We investigated the use of hypergraph
partitioning algorithms for hypertree
decompositions. In this work we implemented and evaluated different hypergraph partitioning algorithms for generation of hypertree decompositions. We investigated the combination of hypergraph partitioning algorithms and the tree
decompositions based algorithms for hypertree
decompositions. We designed and implemented a new local search
algorithm for the unicost set covering problem. This
problem appears when the hypertree decompositions is generated from tree decompositions. We designed and implemented a new general algorithm
for the acyclic hypergraph sandwich problem. This
general algorithm is used for generation of tree and hypertree
decompositions. We theoretically investigated the application of
minimal cuts when using hypergraph partitioning
heuristics for hypertree decomposition. We investigated the complexity of generalized hypertree decomposition. We have found a polynomial time algorithm for
bounded dimension acyclic hypergraph sandwich
problem. We have found a new tractable class of CSP and
compared it with the known tractable classes. We organized a Mini-Workshop on Hypertree
Decompositions. We evaluated the exact algorithm for hypertree
decompositions det-k-decomp on hypergraph
library benchmarks. We investigated the complexity and applications of edge-induced
vertex-cuts. Work about FPT of CSP, considering different parameters. We investigated generalized hypertree
decompositions and the properties of the subclasses of hypergraphs
with bounded generalized hypertree width. We
improved the definitions of the new tractable CSP subclass. We analyzed the complexity of the decision problems for alpha-, beta-,
and gamma-acyclic hypergraphs. We developed and implemented an iterative heuristic algorithm for tree
decompositions and evaluated it on dimacs
instances. We extended the iterative heuristic algorithm for tree decomposition to
generate generalized hypertree decomposition. We implemented a genetic algorithm (GA) and self adaptive GA for tree
and generalized hypertree decompositions. We implemented new branch and bound algorithms and proposed a new lower
bound for generalized hypertree decompositions. We implemented and evaluated an A* algorithms for tree and generalized hypertree decompositions. We performed research on how to apply hypertree
decomposition for shift scheduling problem. We further improved the definitions of both the new
tractable CSP subclass and beta-cover decomposition. We investigate their practical
and theoretical applications. |
|
2006 © Database and Artificial
Intelligence Group, Vienna University of Technology |