Contact Information

Computer Science Department
Colgate University
McGregory Hall, 3rd Floor
13 Oak Drive
Hamilton, NY 13346
(tel) 315.228.7719
Charlotte Jablonski, Administrative Assistant

Event Detail

Dept Tea: Modeling and solving problems with graphs and clique search

Start: Thursday, April 19, 2018, 11:30 a.m.
End: Thursday, April 19, 2018, 12:20 p.m.
Location: 319 McGregory Hall

Speaker: Bogdan Zavalnij, Assistant Professor of Mathematics from University of Pécs, Hungary; currently a Fulbright Scholar-in-Residence at Coker College

Abstract: The aim of mathematical programming is to find a suitable model for a given problem that can aid solving it. There are several well known tool for this aim -- linear programming, SAT, etc. Another approach is to use network representations and algorithms. We will concentrate on one concrete approach from the latter. Namely, modeling problems with auxiliary graphs and solving the problem by finding maximum or k-cliques in it. This talk will show several problems that can be modeled this way and detail the exact method of constructing the auxiliary graph. The audience is expected to have a basic familiarity with graphs.