Gabriele Di Stefano
YOU?
Author Swipe
View article: On Computing Top-$k$ Simple Shortest Paths from a Single Source
On Computing Top-$k$ Simple Shortest Paths from a Single Source Open
We investigate the problem of computing the top-$k$ simple shortest paths in weighted digraphs. While the single-pair variant -- finding the top-$k$ simple shortest paths between two specified vertices -- has been extensively studied over …
View article: Gathering in Non-Vertex-Transitive Graphs Under Round Robin
Gathering in Non-Vertex-Transitive Graphs Under Round Robin Open
The Gathering problem for a swarm of robots asks for a distributed algorithm that brings such entities to a common place, not known in advance. We consider the well-known OBLOT model with robots constrained to move along the edges of a gra…
View article: Burning some myths on privacy properties of social networks against active attacks
Burning some myths on privacy properties of social networks against active attacks Open
This work focuses on showing some arguments addressed to dismantle the extended idea about that social networks completely lacks of privacy properties. We consider the so-called active attacks to the privacy of social networks and the coun…
View article: Mutual and total mutual visibility in hypercube-like graphs
Mutual and total mutual visibility in hypercube-like graphs Open
Let G be a graph and X⊆V(G). Then, vertices x and y of G are X-visible if there exists a shortest x,y-path where no internal vertices belong to X. The set X is a mutual-visibility set of G if every two vertices of X are X-visible, while X …
View article: Colouring a graph with position sets
Colouring a graph with position sets Open
In this paper we consider a colouring version of the general position problem. The \emph{$\gp $-chromatic number} is the smallest number of colours needed to colour the vertices of the graph such that each colour class has the no-three-in-…
View article: Mutual-visibility in strong products of graphs via total mutual-visibility
Mutual-visibility in strong products of graphs via total mutual-visibility Open
Let G be a graph and X⊆V(G). Then X is a mutual-visibility set if each pair of vertices from X is connected by a geodesic with no internal vertex in X. The mutual-visibility number μ(G) of G is the cardinality of a largest mutual-visibilit…
View article: On the approximability of graph visibility problems
On the approximability of graph visibility problems Open
Visibility problems have been investigated for a long time under different assumptions as they pose challenging combinatorial problems and are connected to robot navigation problems. The mutual-visibility problem in a graph $G$ of $n$ vert…
View article: Mutual-visibility problems on graphs of diameter two
Mutual-visibility problems on graphs of diameter two Open
The mutual-visibility problem in a graph G asks for the cardinality of a largest set of vertices S⊆V(G) so that for any two vertices x,y∈S there is a shortest x,y-path P so that all internal vertices of P are not in S. This is also said as…
View article: An optimal algorithm for geodesic mutual visibility on hexagonal grids
An optimal algorithm for geodesic mutual visibility on hexagonal grids Open
For a set of robots (or agents) moving in a graph, two properties are highly desirable: confidentiality (i.e., a message between two agents must not pass through any intermediate agent) and efficiency (i.e., messages are delivered through …
View article: On the general position number of Mycielskian graphs
On the general position number of Mycielskian graphs Open
The general position problem for graphs was inspired by the no-three-in-line problem from discrete geometry. A set S of vertices of a graph G is a general position set if no shortest path in G contains three or more vertices of S. The gene…
View article: Route Planning Algorithms for Fleets of Connected Vehicles: State of the Art, Implementation, and Deployment
Route Planning Algorithms for Fleets of Connected Vehicles: State of the Art, Implementation, and Deployment Open
The introduction of 5G technologies has enabled the possibility of designing and building several new classes of networked information systems that were previously impossible to implement due to limitations on data throughput or the reliab…
View article: Molecular pattern formation on grids in the Moblot model
Molecular pattern formation on grids in the Moblot model Open
In the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the Moblot model has been introduced in order to deal with robots consid…
View article: Lower general position sets in graphs
Lower general position sets in graphs Open
A subset S of vertices of a graph G is a general position set if no shortest path in G contains three or more vertices of S. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the lower general position num…
View article: Mutual-visibility problems on graphs of diameter two
Mutual-visibility problems on graphs of diameter two Open
The mutual-visibility problem in a graph $G$ asks for the cardinality of a largest set of vertices $S\subseteq V(G)$ so that for any two vertices $x,y\in S$ there is a shortest $x,y$-path $P$ so that all internal vertices of $P$ are not in…
View article: The geodesic mutual visibility problem: Oblivious robots on grids and trees
The geodesic mutual visibility problem: Oblivious robots on grids and trees Open
The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robo…
View article: Mutual visibility in hypercube-like graphs
Mutual visibility in hypercube-like graphs Open
Let $G$ be a graph and $X\subseteq V(G)$. Then, vertices $x$ and $y$ of $G$ are $X$-visible if there exists a shortest $u,v$-path where no internal vertices belong to $X$. The set $X$ is a mutual-visibility set of $G$ if every two vertices…
View article: Variety of mutual-visibility problems in graphs
Variety of mutual-visibility problems in graphs Open
If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u,v-path P such that V(P)∩X⊆{u,v}. If each two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibilit…
View article: Time-optimal geodesic mutual visibility of robots on grids within minimum area
Time-optimal geodesic mutual visibility of robots on grids within minimum area Open
The \textsc{Mutual Visibility} is a well-known problem in the context of mobile robots. For a set of $n$ robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no…
View article: Mutual-visibility in distance-hereditary graphs: a linear-time algorithm
Mutual-visibility in distance-hereditary graphs: a linear-time algorithm Open
The concept of mutual-visibility in graphs has been recently introduced. If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u…
View article: Lower General Position Sets in Graphs
Lower General Position Sets in Graphs Open
A subset $S$ of vertices of a graph $G$ is a \emph{general position set} if no shortest path in $G$ contains three or more vertices of $S$. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the \emph{lower…
View article: Variety of mutual-visibility problems in graphs
Variety of mutual-visibility problems in graphs Open
If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u,v\}$. If each two vertices from $X$ are $X$-visible, then $X$ is a mutua…
View article: On the vertex position number of graphs
On the vertex position number of graphs Open
In this paper we generalise the notion of visibility from a point in an integer lattice to the setting of graph theory.For a vertex x of a graph G, we say that a set S ⊆ V (G) is an x-position set if for any y ∈ S the shortest 2 Thankachy,…
View article: On monophonic position sets in graphs
On monophonic position sets in graphs Open
The general position problem in graph theory asks for the largest set S of vertices of a graph G such that no shortest path of G contains more than two vertices of S. In this paper we consider a variant of the general position problem call…
View article: The Geodesic Mutual Visibility Problem for Oblivious Robots: the case of Trees
The Geodesic Mutual Visibility Problem for Oblivious Robots: the case of Trees Open
The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robo…
View article: Mutual-visibility in distance-hereditary graphs: a linear-time algorithm
Mutual-visibility in distance-hereditary graphs: a linear-time algorithm Open
The concept of mutual-visibility in graphs has been recently introduced. If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u, v-path P such that V(P) ∩ X ⊆ {u, v}. If every two vertic…
View article: Molecular Oblivious Robots: A New Model for Robots With Assembling Capabilities
Molecular Oblivious Robots: A New Model for Robots With Assembling Capabilities Open
Research in theoretical swarm robotics focuses on models that assign to robots a minimal set of capabilities. One of the models well investigated is certainly , addressing the case of distributed robots that are, anonymous, without means o…
View article: Mutual-visibility in strong products of graphs via total mutual-visibility
Mutual-visibility in strong products of graphs via total mutual-visibility Open
Let $G$ be a graph and $X\subseteq V(G)$. Then $X$ is a mutual-visibility set if each pair of vertices from $X$ is connected by a geodesic with no internal vertex in $X$. The mutual-visibility number $μ(G)$ of $G$ is the cardinality of a l…