Kedves NLP-sek!
Szeretnem felhivni a figyelmeteket egy a CLP-hez kapcsolodo erdekes
eloadasra, amely holnap, az NLP eloadas utan lesz. Kulonosen azok szamara
ajanlom, akik ereznek egy kis affinitast a grafelmelet/kombinatorika
terulet irant. A reszleteket lasd alabb.
Udv
Szeredi Peter
---------------------------------------------------------------------------
Az eloadas ideje december 6, 14.30-16.00, helye I. epulet 134.
---------------------------------------------------------------------------
Title of the talk: Graph-Based Filtering
Presentation : N. Beldiceanu, Ecole des Mines de Nantes, Franciaország
Joint work with : M. Carlsson, T. Petit, J.-X. Rampon, G. Rochart, C. Truchet
http://www.emn.fr/x-info/ppc/team.html
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/b/Beldiceanu:Nico…
Abstract
Over the past 20 years global (combinatorial) constraints have gradually
been introduced within the area of constraint programming for dealing with
concrete problems. Efficient filtering algorithms, usually based on graph
theory, were developped in an ad-hoc way for each global constraint.
This talk presents a systematic approach which aims at providing generic
filtering algorithms for global constraints. Given a specification of a
global constraint C in terms of graph properties, we show how to derive a
filtering algorithm for C (i.e., check feasibility and eliminate infeasible
choices). For this purpose we present three complementary methods:
(1) The first method is based on the bounds of the graph properties used in
the description of a global constraint. We provide lower and upper
bounds for frequently used graph properties (number of arcs, vertices,
connected components, strongly connected components, sinks).
(2) The second method shows how to determine the status of vertices and
arcs of an intermediate digraph so that the final digraph does not
contain more than (resp. does no contain less than) a given fixed
number of arcs, vertices, connected components, strongly connected
components, or sinks.
(3) The third method presents a database of about 200 graph invariants for
deriving systematically necessary conditions when a global constraint
is defined by more than on graph property.
We conclude with different questions raised by this approach.