Browsing Department of Informatics by Journals "Theory of Computing Systems"

Now showing items 1-6 of 6

    • b-Coloring Parameterized by Clique-Width 

      Jaffke, Lars; Lima, Paloma T.; Lokshtanov, Daniel (Journal article; Peer reviewed, 2023)
      We provide a polynomial-time algorithm for b- Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by ...

    • Lossy Kernelization of Same-Size Clustering 

      Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Purohit, Nidhi; Simonov, Kirill (Journal article; Peer reviewed, 2023)
      In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) ...

    • On the Parameterized Complexity of the Expected Coverage Problem 

      Fomin, Fedor; Ramamoorthi, Vijayaragunathan (Journal article; Peer reviewed, 2022)
      The MAXIMUM COVERING LOCATION PROBLEM (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k ...

    • Second-Order Finite Automata 

      de Melo, Alexsander Andrade; Oliveira, Mateus De Oliveira (Journal article; Peer reviewed, 2022)
      Traditionally, finite automata theory has been used as a framework for the representation of possibly infinite sets of strings. In this work, we introduce the notion of second-order finite automata, a formalism that combines ...

    • Structure of Polynomial-Time Approximation 

      Leeuwen, Erik Jan van; Leeuwen, Jan van (Peer reviewed; Journal article, 2011-10-14)
      Approximation schemes are commonly classified as being either a polynomial-time approximation scheme (ptas) or a fully polynomial-time approximation scheme (fptas). To properly differentiate between approximation schemes ...

    • Typical Sequences Revisited - Computing Width Parameters of Graphs 

      Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2021)
      In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ...