Upcoming Talks

Ist logo

Testing graph properties very quickly

Date: Monday, March 12, 2018 10:00 - 11:00
Speaker: Artur Czumaj (U of Warwick)
Location: Big Seminar room Ground floor / Office Bldg West (I21.EG.101)
Series: Formal Sciences Seminar
Host: Vladimir Kolmogorov
Lab building west seminar room

Abstract:

One of the fundamental algorithmic tasks is to efficiently determine basic properties of graphs or networks.For example, we would like to determine very quickly if the input graph is planar, or is well-clusterable, or to quickly estimate the cost of its minimum spanning tree.While in general, exact versions of these problems can be computationally hard, there have been some recent advances in very fast approximation algorithms for some of these problems.We will present some of the recent results in this area and give examples of some basic graph properties that can be very efficiently tested in the framework of property, often in sublinear-time, and sometimes even in constant time.We will also discuss applications and extensions of these results to some classic optimization problems.
Qr image
Download ICS Download invitation
Back to eventlist