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:LCL problems on grids
Speaker:Janne H. Korhonen
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 10 October 2017
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log*n), or Θ(n), and the design of optimal algorithms can be fully automated.

This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log*n), and Θ(n). In addition to the general complexity result, we classify the complexity of several concrete LCL problems related to colourings and orientations, partially with the help of automated design tools.

Contact
Name(s):Christoph Lenzen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Christoph Lenzen, 10/02/2017 10:28 AMLast modified by:Uwe Brahm/MPII/DE, 10/10/2017 04:01 AM
  • Christoph Lenzen, 10/02/2017 10:29 AM
  • Christoph Lenzen, 10/02/2017 10:28 AM -- Created document.