Blar i Department of Informatics på tidsskrift "Theory of Computing Systems"
Viser treff 1-6 av 6
-
b-Coloring Parameterized by Clique-Width
(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
(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
(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
(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
(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
(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 ...