Department of Informatics: Recent submissions
Now showing items 221-240 of 1130
-
Present-biased optimization
(Journal article; Peer reviewed, 2022)This paper explores the behavior of present-biased agents, that is, agents who erroneously anticipate the costs of future actions compared to their real costs. Specifically, we extend the original framework proposed by ... -
Exact Exponential Algorithms for Clustering Problems
(Journal article; Peer reviewed, 2022)In this paper we initiate a systematic study of exact algorithms for some of the well known clustering problems, namely k-MEDIAN and k-MEANS. In k-MEDIAN, the input consists of a set X of n points belonging to a metric ... -
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms
(Journal article; Peer reviewed, 2022)We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree ... -
(Re)packing Equal Disks into Rectangle
(Journal article; Peer reviewed, 2022)The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following ... -
Detours in Directed Graphs
(Journal article; Peer reviewed, 2022)We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, ... -
FPT Approximation for Fair Minimum-Load Clustering
(Journal article; Peer reviewed, 2022)In this paper, we consider the Minimum-Load k-Clustering/Facility Location (MLkC) problem where we are given a set P of n points in a metric space that we have to cluster and an integer k > 0 that denotes the number of ... -
Convergence of Feedback Arc Set-Based Heuristics for Linear Structural Equation Models
(Journal article; Peer reviewed, 2022)Score-based structure learning in Bayesian networks, where local structures in the graph are given a score and one seeks to recover a high-scoring DAG from data, is an NP-hard problem. While the general learning problem ... -
A Unifying Framework for Characterizing and Computing Width Measures
(Journal article; Peer reviewed, 2022)Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, ... -
Classes of Intersection Digraphs with Good Algorithmic Properties
(Journal article; Peer reviewed, 2022)While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ... -
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width
(Journal article; Peer reviewed, 2022)For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)-dominating set if for all v ∈ S, |N(v) ∩ S| ∈ σ, and for all v ∈ V(G) ⧵ S, |N(v) ∩ S| ∈ ρ. The Min/Max (σ,ρ)-Dominating Set problems ask, given a graph G and ... -
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
(Journal article; Peer reviewed, 2022)In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies ... -
Well-partitioned chordal graphs
(Journal article; Peer reviewed, 2022)We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph G is a well-partitioned chordal graph if there exist a partition P ... -
Taming Graphs with No Large Creatures and Skinny Ladders
(Journal article; Peer reviewed, 2022)We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder ... -
Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory
(Journal article; Peer reviewed, 2022)When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse ... -
Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
(Journal article; Peer reviewed, 2022)The Learning with Errors (LWE) problem receives much attention in cryptography, mainly due to its fundamental significance in post-quantum cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW) algorithm, ... -
Interactive Semantic and Aesthetic Guidance for Multi-View Visualization Design
(Doctoral thesis, 2023-01-09)I det siste har mengden data i omløp blitt stadig større. Det er nyttig å analysere denne dataen ved hjelp av visualisering, men det er også vanskelig for brukere som ikke er eksperter i dette feltet. For å vise mer innblikk ... -
Solving a pickup and delivery routing problem for fourth-party logistics providers
(Journal article; Peer reviewed, 2022)This paper studies a pickup and delivery routing problem for fourth-party logistics providers. The problem aims to schedule routes of vehicles to pick up orders from suppliers and deliver them to factory locations considering ... -
Long-read single-molecule RNA structure sequencing using nanopore
(Journal article; Peer reviewed, 2022)RNA molecules can form secondary and tertiary structures that can regulate their localization and function. Using enzymatic or chemical probing together with high-throughput sequencing, secondary structure can be mapped ... -
Polyhedral results and stronger Lagrangean bounds for stable spanning trees
(Journal article; Peer reviewed, 2023)Given a graph G=(V,E) and a set C of unordered pairs of edges regarded as being in conflict, a stable spanning tree in G is a set of edges T inducing a spanning tree in G, such that for each {ei,ej}∈C, at most one of the ... -
ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth
(Journal article; Peer reviewed, 2022)Given a simplicial complex with n simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study ...