piwik-script

Deutsch Intern
    Chair of Computer Science I - Algorithms, Complexity, and Knowledge-Based Systems

    ICALP Workshop: Constrained Recognition Problems

    -- Organizers: Steven Chaplick  and Ignaz Rutter

    Monday 9-July-2018. Prague, Czech Republic. 

    -- to occur during the 45th International Colloquium on Automata, Languages, and Programming (ICALP). 

    Description

    Recognition is fundamental class of algorithmic problems in the study of discrete structures. Classical examples include testing planarity and testing whether a graph is an interval graph. Often, the goal of such a recognition problem is to construct a representation certifying membership in the class, e.g., a planar embedding or intersection representation by intervals of the real number line. For the past 15 years, this fundamental class of problems has attained a renaissance period where several generalizations have gained prominence. Two primary examples are the classes of graph editing problems and partial representation extension problems. The former widens the class of graphs by allowing k modification operations which can be applied to an input graph in order to fit it into the class. The latter constrains the sought representation by prescribing the exact representation for a subgraph. Recently, there has been significant progress on the editing problems for several standard classes of graphs, e.g., interval graphs [SODA 2016], chordal graphs [SODA 2017, Algorithmica 2016], H-minor free graphs [FOCS 2012], and planar graphs [SODA 2017]. The partial representation extension problem has also been studied for various graph classes, among others planar graphs [TALG 2015], level-planar graphs [SODA 2017], interval graphs [TALG 2015, Algorithmica 2017], and bar visibility graphs [Algorithmica 2017]. The purpose of this workshop is to describe the main techniques employed to obtain recent significant results as well as to highlight the key challenges in these areas.

    Program

    To be determined. 

    Data privacy protection

    By clicking 'OK' you are leaving the web sites of the Julius-Maximilians-Universität Würzburg and will be redirected to Facebook. For information on the collection and processing of data by Facebook, refer to the social network's data privacy statement.

    Data privacy protection

    By clicking 'OK' you are leaving the web sites of the Julius-Maximilians-Universität Würzburg and will be redirected to Twitter. For information on the collection and processing of data by Facebook, refer to the social network's data privacy statement.

    Contact

    Lehrstuhl für Informatik I (Effiziente Algorithmen und wissensbasierte Systeme)
    Am Hubland
    97074 Würzburg

    Phone: +49 931 31-85054
    Email

    Find Contact

    Hubland Süd, Geb. Z8 Hubland Süd, Geb. M2