Department of Informatics
Recent Submissions
-
Longest Cycle above Erdős–Gallai Bound
(Journal article; Peer reviewed, 2024)In 1959, Erdős and Gallai proved that every graph \(G\) with average vertex degree \({\sf ad}(G)\geq 2\) contains a cycle of length at least \({\sf ad}(G)\). We provide an algorithm that for \(k\geq 0\), in time ... -
Stability in Graphs with Matroid Constraints
(Journal article; Peer reviewed, 2024)We study the following INDEPENDENT STABLE SET problem. Let G be an undirected graph and ℳ = (V(G), ℐ) be a matroid whose elements are the vertices of G. For an integer k ≥ 1, the task is to decide whether G contains a set ... -
Breaking a Graph into Connected Components with Small Dominating Sets
(Journal article; Peer reviewed, 2024)We study DOMINATED CLUSTER DELETION. Therein, we are given an undirected graph G = (V,E) and integers k and d and the task is to find a set of at most k vertices such that removing these vertices results in a graph in which ... -
Hybrid k-Clustering: Blending k-Median and k-Center
(Journal article; Peer reviewed, 2024)We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clustering problem, given a set P of points in ℝ^d, an integer k, and a ... -
Cuts in Graphs with Matroid Constraints
(Journal article; Peer reviewed, 2024)Vertex (s, t)-Cut and Vertex Multiway Cut are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given ... -
Computing Tree Decompositions with Small Independence Number
(Journal article; Peer reviewed, 2024)The independence number of a tree decomposition is the maximum of the independence numbers of the subgraphs induced by its bags. The tree-independence number of a graph is the minimum independence number of a tree decomposition ... -
Fixed-Parameter Tractability of Maximum Colored Path and beyond
(Journal article; Peer reviewed, 2024)We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our ... -
MAP- and MLE-Based Teaching
(Journal article; Peer reviewed, 2024)Imagine a learner L who tries to infer a hidden concept from a collection of observations. Building on the work of Ferri et al. (2022), we assume the learner to be parameterized by priors P (c) and by c-conditional likelihoods ... -
FPT approximation and subexponential algorithms for covering few or many edges
(Journal article; Peer reviewed, 2024)We study the 𝛼-FIXED CARDINALITY GRAPH PARTITIONING (𝛼-FCGP) problem, the generic local graph partitioning problem introduced by Bonnet et al. [Algorithmica 2015]. In this problem, we are given a graph 𝐺, two numbers ... -
Low-Complexity Hardware Architecture of APN Permutations Using TU-Decomposition
(Journal article; Peer reviewed, 2024)Functions with good cryptographic properties which are used as S-boxes in the design of block ciphers have a fundamental importance to the security of these ciphers since they determine the resistance to various kinds of ... -
Approximating Long Cycle Above Dirac’s Guarantee
(Journal article; Peer reviewed, 2024)Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better ... -
Parameterized complexity of broadcasting in graphs
(Journal article; Peer reviewed, 2024)The task of the broadcast problem is, given a graph 𝐺 and a source vertex 𝑠, to compute the minimum number of rounds required to disseminate a piece of information from 𝑠 to all vertices in the graph. It is assumed that, ... -
Diverse Pairs of Matchings
(Journal article; Peer reviewed, 2024)We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maxi- mum/perfect) matchings whose symmetric difference is at least k. Diverse ... -
(Re)packing Equal Disks into Rectangle
(Journal article; Peer reviewed, 2024)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 ... -
Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks
(Journal article; Peer reviewed, 2024)Identifying a maximum independent set is a fundamental NP-hard problem. This problem has several real-world applications and requires finding the largest possible set of vertices not adjacent to each other in an undirected ... -
Graph Neural Networks in Algorithm Engineering
(Doctoral thesis, 2025-03-27)Graf Nevrale Nettverk (GNN) er ny teknologi innen kunstig intelligens. GNN viderefører de vellykkede ideene fra konvensjonell dyplæring til å fungere på grafer. For ulike grafteoretiske problemer har GNN blitt et nytt ... -
PACE Solver Description: LUNCH - Linear Uncrossing Heuristics
(Journal article; Peer reviewed, 2024)The 2024 PACE challenge is on One-Sided Crossing Minimization: Given a bipartite graph with one fixed and one free layer, compute an ordering of the vertices in the free layer that minimizes the number of edge crossings ... -
The category of iterative sets in homotopy type theory and univalent foundations
(Journal article; Peer reviewed, 2024)When working in homotopy type theory and univalent foundations, the traditional role of the category of sets, Set, is replaced by the category hSet of homotopy sets (h-sets); types with h-propositional identity types. Many ... -
First-Order Temporal Logic on Finite Traces: Semantic Properties, Decidable Fragments, and Applications
(Journal article; Peer reviewed, 2024)Formalisms based on temporal logics interpreted over finite strict linear orders, known in the literature as finite traces, have been used for temporal specification in automated planning, process modelling, (runtime) ... -
Tool-Augmented Human Creativity
(Journal article; Peer reviewed, 2024)Creativity is the hallmark of human intelligence. Roli et al. (Frontiers in Ecology and Evolution 9:806283, 2022) state that algorithms cannot achieve human creativity. This paper analyzes cooperation between humans and ...
RSS 2.0