Campus Event Calendar
Event Entry
What and Who
LCL problems on grids
Janne H. Korhonen
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 10 October 2017
13:00
30 Minutes
E1 4
024
Saarbrücken
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
Christoph Lenzen
--email hidden
passcode not visible
logged in users only
Christoph Lenzen, 10/02/2017 10:29
Christoph Lenzen, 10/02/2017 10:28 -- Created document.
Christoph Lenzen, 10/02/2017 10:28 -- Created document.