A very informal workshop that will consist of few presentations with plenty of time
for discussions and exchanges. Admission is free,
but there will be no reimbursements for travel and local costs.
We encourage you to participate not only with your most recent results
but also with a list of open and interesting problems.
Please feel free to ask for any further information e-mailing one of the member of the organizing committee. If you intend to come please mail to Marco Budinich your travel schedule and hotel reservation request at your earliest convenience.
Venue of the meeting is the 'Physics Department' that is part of the of the University of Trieste and is located in Via Valerio 2 - Trieste - Italy. To reach it from downtown take the bus 17 (direction 'S. Cilino') and get down at the University. Our department is a red-bricks building located just in front of a huge 'Agip' gas station (have a glimpse at it from Physics Department homepage) and the 17 bus stop is just in front of it.
The Organizing Committee
Immanuel Bomze - I.S.O.C. University of Vienna - <bomze@smc.univie.ac.at>
Marco Budinich - Physics Department,University of Trieste - <mbh@trieste.infn.it> <-- local organizer
and
Marcello Pelillo - University of Venice "Ca' Foscari" - <pelillo@dsi.unive.it>
Tuesday June 17, 1997
9:00 - 12:30 : Arrivals & meet together
12:30 - 14:15 : Lunch
14:15 - 15:00 : M. Pelillo (Venice, Italy) - Replicator equations, maximum cliques,
and graph matching problems
15:00 - 15:45 : M. Budinich (Trieste, Italy) - Properties of the adjacency matrix and
the maximum clique problem
15:45 - 16:15 : Coffee break
16:15 - 17:00 : F. Rendl (Graz, Austria) - Semidefinite programming and max-clique
approximations
17:00 - 17:45 : Discussion
20:00 - ... : Dinner
Wednesday June 18, 1997
9:30 - 10:15 : I. Bomze (Wien, Austria) - Evolution towards the maximum clique
10:15 - 11:00 : V. Stix (Wien, Austria) - Evolutionary dynamics approach to
enlarging cliques with independent sets
11:00 - 11:30 : Coffee break
11:30 - 12:15 : E. Stella (Bari, Italy) - Mobile robot Navigation and Maximum Clique
12:15 - 13:00 : G. Grossi (Milano, Italy) - Discrete Neural Algorithm for the Maximum
Clique Problem: Analysis and Circuit
Implementation (Abstract)
13:00 - 14:30 : Lunch
Afternoon : Further discussions & departures
(contains general info, hotel, flights etc. by Alessandra Richetti)
Discrete Neural Algorithm for the Maximum Clique Problem:
Analysis and Circuit Implementation
Giuliano Grossi (Milano, Italy)
For the Maximum
Clique problem we propose a neural approximation algorithm that can
be implemented on Field Programmable Gate Arrays (FPGA). The
algorithm builds a sequence of discrete
Hopfield's networks that, in polynomial time, converge to a state
representing a clique for a given graph. Some experiments made on
the DIMACS benchmark show that the approximated solutions found are
satisfactory.
Moreover the simplicity of the algorithm makes it easy to design a
uniform family of circuits of small size (about 10 n^2 log n).