anstelle von Herrn Prof. Podelski, dessen Vortrag zum Thema "Abstraction
Refinement for Software Model Checking" auf das kommende Wintersemester
verlegt wurde, spricht am Montag, den 8.7.02 um 16 c. t. im Gebäude 45,
HS 003
Herr Sven Thiel
zum Thema
Efficient Enumeration of the Solved Forms of Dominance Graphs
Abstract
The dominance relation of a tree is the ancestor-descendant relation of
its nodes. We consider the following problem: We are given a collection
of tree fragments and a set of constraints like "node u has to be an
ancestor of node v". Can one assemble the fragments to a tree such that
all constraints are fullfilled? We show how to model this problem by a
dominance graph. Then we present a linear time algorithm for deciding
solvability. Based upon this algorithm we develop an efficient algorithm
for enumerating all solved forms of a dominance graph.
Am kommenden Freitag, den 5.7.02, spricht Herr Rene Beier zum Thema
"Energy Optimal Routing in Radio Networks".
Alle InteressentInnen sind zu den Vorträgen herzlich eingeladen.
Die Veranstaltung wird gemeinsam von der Fachrichtung Informatik und der
International Max Planck Research School getragen.