Workshop on Graph and Hypergraph Decompositions

December  16-18, 2004

Vienna, Austria

Home       Participants      Programme      Travel      Social Events      Organizers

Workshop Programme


Thursday, December 16, 2004


08:30-09:30: Registration


09:30–09:45: Welcome Plenary Session (Chair: Georg Gottlob)



Session1: Graph and Hypergraph Decompositions and Constraint Satisfaction



09:45-10:30: Exploiting tree-decomposition in search: the AND/OR paradigm, Rina Dechter

10:30-11:00: Hinges then Hypertrees are nearly optimal, Dave Cohen


11:00-11:30: Refreshments


11:30-11:45: Graph and Hypergraph Decomposition Research at 4C, Brahim Hnich

11:45-12:15: Dulmage-Mendelsohn decompositions and SAT, Stefan Szeider


12:15-13:30: Lunch           



Session 2a: Hypertree Decompositions



13:30-14:15: Hypertree width and its extensions, Francesco Scarcello

14:15-14:45: Heuristic Approaches for Hypertree Decomposition, Artan Dermaku and Marko Samer


14:45-15:15: Refreshments


Session 2b: Trees and  Queries



15:15-15:45: Generalized Projection Pushing Revisited, Ben McMahan

15:45-16:15: Invariant Queries and Characterizations of Definability, Michael Benedikt



Friday, December 17,  2004


Session 3:  Clique-Width and Acyclicity



 09:30-10:15: Graph and hypergraph decomposition and maximum weight stable sets, Andreas Brandstädt

10:15-10:45: Clique width, patchwidth and rankwidth:choosing the right notions, Johann Makowsky


10:45-11:15: Refreshments


11:15-12:00: Recognizing graphs of rank-width at most k,  Sang-il Oum

12:00-12:30: Acyclicity and Hypertree-Width versus Clique-Width, Reinhard Pichler


12:15-14:00: Lunch           


Session 4a:  Hypergraphs and Queries



14:00-14:30: The complexity of generalized acyclic conjunctive queries, Arnaud Durand

14:30-15:00: Efficient implementation of acyclic conjunctive queries with restricted comparisons, Etienne Grandjean


15:00-15:30: Refreshments


Session 4b:  Hypertree and Tree Decompositions



15:30-16:15: Generalized Hyper-Treewidth, Games, and Connectivity, Martin Grohe

16:15-16:45: To be announced, Georg Gottlob

16:45-17:15: Tree decomposition in discrete optimization, Oleg Shcherbina



Saturday, December 18,  2004


Session 5: Complexity of Directed Graphs, Geometrical Aspects of Hypergraphs, Matroids



09:30-10:15: Entanglement -- A Measure for the Complexity of Directed Graphs, with Applications to Logic and Games, Erich Grädel and Dietmar Berwanger 


10:15-11:00: Tree Decompositions -- Why Matroids are Useful, Petr Hlineny


11:00-11:30: Refreshments


11:30-12:15:  Geometrical Aspects of Hypergraphs, Alain Bretto 


12:15: CLOSE, Lunch           



2004 ©  Database and Artificial Intelligence Group, Vienna University of Technology   Webmaster