Browsing Department of Informatics by Issue Date
Now showing items 41-60 of 925
-
Fine-grained parameterized complexity analysis of graph coloring problems
(Journal article; Peer reviewed, 2023)The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q- Coloring with respect to a hierarchy of structural ... -
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 ... -
FAIR+E pathogen data for surveillance and research: lessons from COVID-19
(Journal article; Peer reviewed, 2023)The COVID-19 pandemic has exemplified the importance of interoperable and equitable data sharing for global surveillance and to support research. While many challenges could be overcome, at least in some countries, many ... -
Order Reconfiguration under Width Constraints
(Journal article; Peer reviewed, 2023)In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω′ of the vertices of G, can one transform ω into ω′ by a sequence of swaps of adjacent elements in ... -
Finding haplotypic signatures in proteins
(Journal article; Peer reviewed, 2023)Background The nonrandom distribution of alleles of common genomic variants produces haplotypes, which are fundamental in medical and population genetic studies. Consequently, protein-coding genes with different ... -
Measuring Adversarial Robustness using a Voronoi-Epsilon Adversary
(Journal article; Peer reviewed, 2023)Previous studies on robustness have argued that there is a tradeoff between accuracy and adversarial accuracy. The tradeoff can be inevitable even when we neglect generalization. We argue that the tradeoff is inherent to ... -
Further investigations on permutation based constructions of bent functions
(Journal article; Peer reviewed, 2023)Constructing bent functions by composing a Boolean function with a permutation was introduced by Hou and Langevin in 1997. The approach appears simple but heavily depends on the construction of desirable permutations. In ... -
Treewidth is NP-Complete on Cubic Graphs
(Journal article; Peer reviewed, 2023)In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new ... -
Graph Algebras and Derived Graph Operations
(Journal article, 2023)We revise our former definition of graph operations and correspondingly adapt the construction of graph term algebras. As a first contribution to a prospective research field, Universal Graph Algebra, we generalize some ... -
Convexity, convolution and competitive equilibrium
(Journal article; Peer reviewed, 2023)This paper considers a chief interface between mathematical programming and economics, namely: money-based trade of perfectly divisible and transferable goods. Three important and related features are singled out here: ... -
Mining EL⊥ Bases with Adaptable Role Depth
(Journal article; Peer reviewed, 2023)In Formal Concept Analysis, a base for a finite structure is a set of implications that characterizes all valid implications of the structure. This notion can be adapted to the context of Description Logic, where the base ... -
On the maximum number of edges in planar graphs of bounded degree and matching number
(Journal article; Peer reviewed, 2023)We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number. -
Covering Radius of Generalized Zetterberg Type Codes Over Finite Fields of Odd Characteristic
(Journal article; Peer reviewed, 2023)Let Fq0 be a finite field of odd characteristic. For an integer s≥1 , let Cs(q0) be the generalized Zetterberg code of length qs0+1 over Fq0 . If s is even, then we prove that the covering radius of Cs(q0) is 3. Put q=qs0 ... -
New Results on the -1 Conjecture on Cross-Correlation of m-Sequences Based on Complete Permutation Polynomials
(Journal article; Peer reviewed, 2023)The cross-correlation between two maximum length sequences (m-sequences) of the same period has been studied since the end of 1960s. One open conjecture by Helleseth states that the cross- correlation between any two p-ary ... -
Detours in directed graphs
(Journal article; Peer reviewed, 2023)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, ... -
Annotating otoliths with a deep generative model
(Journal article; Peer reviewed, 2023)Otoliths are a central information source for fish ecology and stock management, conveying important data about age and other life history for individual fish. Traditionally, interpretation of otoliths has required skilled ... -
Classes of intersection digraphs with good algorithmic properties
(Journal article; Peer reviewed, 2023)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 ... -
Parameterized complexity of categorical clustering with size constraints
(Journal article; Peer reviewed, 2023) -
Diverse collections in matroids and graphs
(Journal article; Peer reviewed, 2023)We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω : ... -
Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
(Journal article; Peer reviewed, 2023)We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider, play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some ...