Hypertree

Complementary Approaches to Constraint Satisfaction

Home Members Publications Software downloads Work Progress

Peer-reviewed Publications

Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, and Francesco Scarcello. Hypertree Decompositions: Structure, Algorithms, and Applications, International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05)", Metz, France, 2005, (Lecture Notes in Computer Science, Volume 3787, pages 1 – 15, 2005, Springer-Verlag Heidelberg).

Georg Gottlob, Gianluigi Greco, Francesco Scarcello: The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions. IJCAI 2005: 150-155

Georg Gottlob, Gianluigi Greco, Francesco Scarcello. Pure Nash Equilibria: Hard and Easy Games. Journal of Artificial Intelligence Research 24 (2005) 357-406.

Georg Gottlob: Computing Cores for Data Exchange: New Algoritms and Practical Solutions. Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems PODS '05, pages 148-159.

Marko Samer. Hypertree-decomposition via Branch-decomposition, 19th International Joint Conference on Artificial Intelligence (IJCAI 2005), pages 1535-1536, 2005.

Nysret Musliu. Local search algorithm for unicost set covering problem, The 19th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems (IEA/AIE'06), Annecy, FRANCE, 2006 (Lecture Notes in Artificial Intelligence (LNAI),Volume 4031 , pages 302-311, 2006, Springer).

Marko Samer and Stefan Szeider. Constraint Satisfaction with Bounded Treewidth Revisited. 12th International Conference on Principles and Practice of Constraint Programming (CP06), volume 4204 of LNCS, pages 499-513. Springer-Verlag, 2006.

Nysret Musliu. Generation of Tree Decompositions by Iterated Local Search. EvoCOP 2007 - Seventh European Conference on Evolutionary Computation in Combinatorial Optimisation, LNCS, Volume 4446, pages 130-141, 2007, Springer. (in press)

Georg Gottlob, Zoltan Miklos and Thomas Schwentick. Generalized hypertree decompositions: NP-Hardness and Tractable Variants. Proceedings of the 26th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, to appear.

Nysret Musliu. Tabu Search for Generalized Hypertree Decompositions. The Seventh Metaheuristics International Conference (MIC), Montreal, June 25-29, 2007.

Nysret Musliu and Werner Schafhauser. Genetic Algorithms for Generalized Hypertree Decompositions. European Journal of Industrial Engineering, Volume1 No.3, pp. 317-340, 2007.

Nysret Musliu. An Iterative Heuristic Algorithm for Tree Decomposition. Studies in Computational Intelligence: Recent Advances in Evolutionary Computation for Combinatorial Optimization, Springer, 2008. Carlos Cotta, Jano van Hemert (Eds.)

Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, Marko Samer. Heuristic Methods for Hypertree Decompositions. MICAI 2008. Lecture Notes in Artificial Intelligence, 2008, to appear.

Georg Gottlob and Marko Samer. A Backtracking-Based Algorithm for Hypertree Decomposition. ACM Journal of Experimental Algorithmics (JEA) 13:1.1-1.19, 2008.

Research Reports

Tobias Ganzow, Georg Gottlob, Nysret Musliu, Marko Samer. A CSP Hypergraph Library, DBAI-TR-2005-50, Technische Universität Wien, 2005.

Vladimir Gurvich, Nysret Musliu, Vladimir Oudalov. An algorithm for the acyclic hypergraph sandwich problem, DBAI-TR-2005-52, Technische Universität Wien, 2005.

Artan Dermaku, Tobias Ganzow, Georg Gottlob, Ben McMahan, Nysret Musliu, Marko Samer. Heuristic Methods for Hypertree Decompositions, DBAI-TR-2005-53, Technische Universität Wien, 2005.

Marko Samer and Stefan Szeider. Complexity and Applications of Edge-Induced Vertex-Cuts. Technical Report arXiv:cs.DM/0607109, 2006.

Georg Gottlob, Zoltan Miklos, Thomas Schwentick. Generalized Hypertree Decompositions:NP-Hardness and Tractable Variants, DBAI-TR-2007-55,Technische Universität Wien, 2007.

Master thesis

Werner Schafhauser. New Heuristic Methods for Tree Decompositions and Generalized Hypertree Decompositions, Master thesis, Database and Artificial Intelligence Group, Vienna University of Technology, 2006.

Artan Dermaku. Generalized Hypertree Decompositions based on Hypergraph Partitioning, Master thesis, Database and Artificial Intelligence Group,Vienna University of Technology, 2007.

In preparation…

Georg Gottlob, Thomas Schwentick, Zoltan Miklos. Component decomposition, DBAI-TR-2006-54, Technische Universität Wien, 2006.

Georg Gottlob, Vladimir Gurvich, Zoltan Miklos On the complexity of the acyclic hypergraph sandwich problem. DBAI-TR-2005-51, Technische Universität Wien, 2005.

2006 © Database and Artificial Intelligence Group, Vienna University of Technology