Γενικό Σεμινάριο Τμήματος 22η Ομιλία

Το Γενικό Σεμινάριο Τμήματος συνεχίζεται αύριο, Τετάρτη 7/5, με την ένατη ομιλία του Εαρινού εξαμήνου, η οποία θα γίνει στην αίθουσα 342, ώρα 14:00 – 15:00. Οι λεπτομέρειες της ομιλίας:

Ομιλητής: Χριστόφορος Ραπτόπουλος (Πανεπιστήμιο Πατρών)

Τίτλος ομιλίας: The MAX-CLIQUE problem on random graphs

Περίληψη: Finding a maximum clique in a graph is a classic and notoriously difficult problem in theoretical computer science. Its decision version is NP-complete, meaning that no efficient algorithm is known to solve it in the general case. In this talk, we explore the MAX-CLIQUE problem when the input graph is drawn from a probability distribution over the space of all graphs. We will outline key ideas behind existence proofs and highlight the design of breakthrough algorithms in this probabilistic setting. Additionally, we will discuss several longstanding open problems. Time permitting, we will also present some recent results in this area.

Μετά το πέρας της ομιλίας θα υπάρχουν καφές, χυμοί και μπισκότα για τους παρευρισκόμενους.

Εκ μέρους της επιτροπής σεμιναρίου,

Δημήτρης

Πηγή