8 papers
Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä +1
The neighbourhood complexity of a graph is a quantity measuring, for a graph and an integer , the maximum possible number (over all vertex subsets of size…
The Size of the Intersection of -ary Hamming Balls
Ville Junnila, Tero Laihonen, Tuomo Lehtilä +1
The interest in studying the size of the intersection of multiple -ary Hamming balls has grown due to the recent advances in DNA-based data storage systems. We present an exact…
Identifying codes in graphs of given maximum degree: Characterizing trees
Dipayan Chakraborty, Florent Foucaud, Michael A. Henning +1
An identifying code of a closed-twin-free graph is a dominating set of vertices of such that any two vertices in have a distinct intersection between their closed n…
New Optimal Results on Codes for Location in Graphs
Ville Junnila, Tero Laihonen, Tuomo Lehtilä +1
In this paper, we broaden the understanding of the recently introduced concepts of solid-locating-dominating and self-locating-dominating codes in various graphs. In particular, we…
Levenshtein's Sequence Reconstruction Problem and Results for Larger Alphabet Sizes
Ville Junnila, Tero Laihonen, Tuomo Lehtilä
The problem of storing large amounts of information safely for a long period of time has become essential. One of the most promising new data storage mediums are the polymer-based…
The Generalized Double Pouring Problem: Analysis, Bounds and Algorithms
Gerold Jäger, Tuomo Lehtilä
We consider a logical puzzle which we call double pouring problem, which was original defined for vessels. We generalize this definition to as follows. Each of the…