演講公告

演講主題：Probabilistic analysis of an exhaustive search algorithm in random graphs
主講人：Prof. Vytas Zacharovas (Vilnius University)
演講日期：2010年12月20日(星期一) 下午1：30 ~ 2：20
演講地點：(光復校區)科學一館213室
摘要內容：
The problem of finding maximum independent sets appears in many applications of graph theory.
The main result of the talk is the estimate for the mean value of steps that are needed to complete the exhaustive search algorithm on a radom graph generated according to Erdős–Rényi model G(n,p).
Obtaining any rigorous result on the higher moments or the limit distribution of the number of steps in the exhaustive search algorithm turns out to be very difficult. We will discuss some heuristic arguments that allow us to conjecture the existence and the form of the limit distribution.
相關檔案：演講991220(離).doc

$返回$ go back