BLBastian Laubner

Bastian Laubner

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Bastian Laubner has a total of 2 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Capturing Polynomial Time on Interval Graphs

    by Bastian Laubner

    We prove a characterization of all polynomial-time computable queries on the class of interval graphs by sentences of fixed-point logic with counting. More precisely, it is shown that on the class of unordered interval graphs, any query is polynomial-time computable if and only if it is definable in fixed-point logic with counting. This result is one of the first establishing the capturing of polynomial time on a graph class which is defined by forbidden induced subgraphs. For this, we define a canonical form of interval graphs using a type of modular decomposition, which is different from the method of tree decomposition that is used in most known capturing results for other graph classes, specifically those defined by forbidden minors. The method might also be of independent interest for its conceptual simplicity. Furthermore, it is shown that fixed-point logic with counting is not expressive enough to capture polynomial time on the classes of chordal graphs or incomparability graphs.

  • Open Access

    A combinatorial classification of postsingularly finite complex exponential maps

    by Bastian Laubner, Dierk Schleicher, Vlad Vicol

    We give a combinatorial classification of postsingularly finite exponential maps in terms of external addresses starting with the entry $0$. This extends the classification results for critically preperiodic polynomials [2] to exponential maps. Our proof relies on the topological characterization of postsingularly finite exponential maps given recently in [14]. These results illustrate once again the fruitful interplay between combinatorics, topology and complex structure which has often been successful in complex dynamics.