BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20221128T112053Z
UID:Seminar-ACTO-998@lxserverA.csc.liv.ac.uk
ORGANIZER:CN=Igor Potapov:MAILTO:potapov@liverpool.ac.uk
DTSTART:20210526T140000
DTEND:20210526T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Maurice Chandoo: Descriptive Complexity of Graph Classes via Labeling Schemes\n\nLabeling schemes are space-efficient data structures that can be used to represent graphs from certain classes such as planar graphs or interval graphs. The idea is to assign short labels to each vertex of a graph such that the adjacency of two vertices can be computed from their labels. The algorithm which computes this is called label decoding algorithm. The time complexity of this algorithm should be low since it corresponds to the time to query an edge in the graph.\n\n\n\nIf we restrict the complexity of the label decoding algorithm, what graph classes still admit a labeling scheme? Surprisingly, even if the label decoder must be computable by a family of boolean circuits of constant-depth and polynomial size (AC0), every natural (=hereditary) graph class which is known to have a labeling scheme still can be found in this class. Alternatively, the label decoders of many labeling schemes can be described by FO formulas. Therefore FOL provides a different and in a sense more restrictive framework from classical complexity classes that can be used to analyze the descriptive complexity of graph classes. \n\n\n\nIn this talk I will give a general introduction to labeling schemes, different complexity classes of graph classes defined in terms of labeling schemes and graph parameters such as tree-width, how they relate and some basic properties. Moreover, a reduction notion among graph classes is described that makes it possible to apply the concept of completeness in this context. Finally, some complexity- and graph-theoretic research questions in this direction are presented.\n\n\n\nThe estimated talk time is 30min.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=998
LOCATION:
END:VEVENT
END:VCALENDAR