7 citations · 18 across the 14 of their papers we have counts for
16 papers
Optimal -locating-dominating codes in infinite triangular grid
Soura Sena Das, Tuomo Lehtilä, Sagnik Sen
We study two variants of location-domination in infinite triangular grids which allow locating up to vertices simultaneously. A locating-dominating code is a dominating…
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…
Unique Insertion Error Patterns in Levenshtein's Reconstruction Problem
Ville Junnila, Tero Laihonen, Tuomo Lehtilä +1
Levenshtein's sequence reconstruction model plays an essential role in information retrieval of advanced memory systems, such as the DNA-based storage systems. In the model, a word…
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…
Partition strategies for the Maker-Breaker domination game
Guillaume Bagan, Eric Duchêne, Valentin Gledel +2
The Maker-Breaker domination game is a positional game played on a graph by two players called Dominator and Staller. The players alternately select a vertex of the graph that has…
On Unique Error Patterns in the Levenshtein's Sequence Reconstruction Model
Ville Junnila, Tero Laihonen, Tuomo Lehtilä
In the Levenshtein's sequence reconstruction problem a codeword is transmitted through channels and in each channel a set of errors is introduced to the transmitted word. In pr…
Identifying codes in triangle-free graphs of bounded maximum degree
Dipayan Chakraborty, Florent Foucaud, Michael A. Henning +1
An identifying code of a closed-twin-free graph is a set of vertices of such that any two vertices in have a distinct, nonempty intersection between their closed ne…
Resolving Sets in Temporal Graphs
Jan Bok, Antoine Dailly, Tuomo Lehtilä
A \emph{resolving set} in a graph is a set of vertices such that every vertex of is uniquely identified by its distances to the vertices of . Introduced in the 1970s…
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ä
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…
Optimal local identifying and local locating-dominating codes
Pyry Herva, Tero Laihonen, Tuomo Lehtilä
We introduce two new classes of covering codes in graphs for every positive integer . These new codes are called local -identifying and local -locating-dominating codes an…
Neighbourhood complexity of graphs of bounded twin-width
Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä +1
We give essentially tight bounds for, , the maximum number of distinct neighbourhoods on a set of vertices in a graph with twin-width at most~. Using the celebra…
The RED-BLUE SEPARATION problem on graphs
Subhadeep Ranjan Dev, Sanjana Dey, Florent Foucaud +2
We introduce the Red-Blue Separation problem on graphs, where we are given a graph whose vertices are colored either red or blue, and we want to select a (small) subset $…
Bounds and extremal graphs for total dominating identifying codes
Florent Foucaud, Tuomo Lehtilä
An identifying code of a graph is a dominating set of such that any two distinct vertices of have distinct closed neighbourhoods within . The smallest size of an…
Revisiting and improving upper bounds for identifying codes
Florent Foucaud, Tuomo Lehtilä
An identifying code of a graph is a dominating set of such that any two distinct vertices of have distinct closed neighbourhoods within . These codes have been w…
Locating-dominating sets: from graphs to oriented graphs
Nicolas Bousquet, Quentin Deschamps, Tuomo Lehtilä +1
A locating-dominating set in an undirected graph is a subset of vertices such that is dominating and for every , we have . In this p…