|
|
|
Workshop on Graph and Hypergraph
Decompositions December 16-18, 2004 |
|
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 Chair: 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 Chair: 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 Chair: 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 Chair: 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 Chair: 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 Chair: 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 Chair: 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 |