Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Parameterized Algorithms and the Structure of Networks
Speaker:Erik Jan van Leeuwen
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Joint Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Language:English
Date, Time and Location
Date:Wednesday, 13 January 2016
Time:12:15
Duration:60 Minutes
Location:Saarbrücken
Building:E1 5
Room:002
Abstract
How many friends do you have? Are you and I friends, or friends of common friends, or friends of friends of friends? What is the largest group of your friends that are also friends of each other? Well-known algorithms exist to efficiently compute the answer to the first two questions. Stunningly, no algorithm is likely to exist that efficiently answers the third question. A major caveat, however, is that this last observation assumes that we have no specific knowledge about the network.

In this talk, I will investigate how knowledge of the structure of a network can be exploited in the quest for efficient algorithms. I will also employ a novel paradigm in algorithm design and analysis called parameterized algorithms. In recent work, I combined this paradigm with structural properties of networks to achieve fine-grained dichotomies for the algorithmic complexity of many problems. In particular, I will take you on a journey from the Clique problem in social networks to the Dominating Set problem in an intriguing class of networks called t-claw-free graphs.
Contact
Name(s):Jennifer Müller
Phone:2900
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created by:Jennifer Müller/MPI-INF, 09/01/2015 09:46 AMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Jennifer Müller, 01/06/2016 11:27 AM
  • Jennifer Müller, 09/01/2015 09:48 AM -- Created document.