25 citations · 112 across the 30 of their papers we have counts for
41 papers
Computing in Anonymous Dynamic Networks with One-Bit Communications
Thibaut Blanc, Giuseppe Antonio Di Luna, Giovanni Viglietta
We initiate the study of deterministic computation in anonymous dynamic networks where each agent broadcasts one bit per round and receives only the number of neighbors broadcastin…
Efficient Lifting of Discrete Logarithms Modulo Prime Powers
Giovanni Viglietta, Yasuyuki Kachi
We present a deterministic algorithm that, given a prime and a solution to the discrete logarithm problem with , efficiently…
Minimal Arrangements of Spherical Geodesics
Giovanni Viglietta
We study arrangements of geodesic arcs on a sphere, where all arcs are internally disjoint and each arc has its endpoints located within the interior of other arcs. We establish fu…
Efficient Computation in Congested Anonymous Dynamic Networks
Giuseppe A. Di Luna, Giovanni Viglietta
An anonymous dynamic network is a network of indistinguishable processes whose communication links may appear or disappear unpredictably over time. Previous research has shown that…
Minimizing Visible Edges in Polyhedra
Csaba D. Tóth, Jorge Urrutia, Giovanni Viglietta
We prove that, given a polyhedron in , every point in that does not see any vertex of must see eight or more edges of $\mathca…
Optimal Computation in Anonymous Dynamic Networks
Giuseppe A. Di Luna, Giovanni Viglietta
We give a simple characterization of the functions that can be computed deterministically by anonymous processes in dynamic networks, depending on the number of leaders in the netw…
Computing in Anonymous Dynamic Networks Is Linear
Giuseppe A. Di Luna, Giovanni Viglietta
We give the first linear-time counting algorithm for processes in anonymous 1-interval-connected dynamic networks with a leader. As a byproduct, we are able to compute in roun…
Pushing Blocks by Sweeping Lines
Hugo A. Akitaya, Maarten Löffler, Giovanni Viglietta
We investigate the reconfiguration of blocks, or "tokens", in the square grid using "line pushes". A line push is performed from one of the four cardinal directions and pushes…
A Theory of Spherical Diagrams
Giovanni Viglietta
We introduce an axiomatic theory of spherical diagrams as a tool to study certain combinatorial properties of polyhedra in , which are of central interest in the conte…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Cyclic Shift Problems on Graphs
Kwon Kham Sai, Ryuhei Uehara, Giovanni Viglietta
We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished c…
Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots
Giuseppe A. Di Luna, Ryuhei Uehara, Giovanni Viglietta +1
A swarm of anonymous oblivious mobile robots, operating in deterministic Look-Compute-Move cycles, is confined within a circular track. All robots agree on the clockwise direction…
Mobile RAM and Shape Formation by Programmable Particles
Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro +2
We investigate computational issues in the distributed model Amoebots of programmable matter. In this model, the computational entities, called particles, are anonymous finite-stat…
Oblivious Permutations on the Plane
Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini +3
We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous,…
TuringMobile: A Turing Machine of Oblivious Mobile Robots with Limited Visibility and its Applications
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro +1
In this paper we investigate the computational power of a set of mobile robots with limited visibility. At each iteration, a robot takes a snapshot of its surroundings, uses the sn…
Optimally Guarding 2-Reflex Orthogonal Polyhedra by Reflex Edge Guards
Giovanni Viglietta
Let an orthogonal polyhedron be the union of a finite set of boxes in (i.e., cuboids with edges parallel to the coordinate axes), whose surface is a connected 2-manif…
Line-Recovery by Programmable Particles
Giuseppe Di Luna, Paola Flocchini, Giuseppe Prencipe +2
Shape formation has been recently studied in distributed systems of programmable particles. In this paper we consider the shape recovery problem of restoring the shape when of…
Shape Formation by Programmable Particles
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro +2
Shape formation is a basic distributed problem for systems of computational mobile entities. Intensively studied for systems of autonomous mobile robots, it has recently been inves…
Meeting in a Polygon by Anonymous Oblivious Robots
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro +2
The Meeting problem for searchers in a polygon (possibly with holes) consists in making the searchers move within , according to a distributed algorithm, in such a…
Gathering in Dynamic Rings
Giuseppe Antonio Di Luna, Paola Flocchini, Linda Pagli +3
The gathering problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advance…
Population Protocols with Faulty Interactions: the Impact of a Leader
Giuseppe Antonio Di Luna, Paola Flocchini, Taisuke Izumi +3
We consider the problem of simulating traditional population protocols under weaker models of communication, which include one-way interactions (as opposed to two-way interactions)…
On the Power of Weaker Pairwise Interaction: Fault-Tolerant Simulation of Population Protocols
Giuseppe Antonio Di Luna, Paola Flocchini, Taisuke Izumi +3
In this paper we investigate the computational power of Population Protocols (PP) under some unreliable and/or weaker interaction models. More precisely, we focus on two features r…
Square Formation by Asynchronous Oblivious Robots
Marcello Mamino, Giovanni Viglietta
A fundamental problem in Distributed Computing is the Pattern Formation problem, where some independent mobile entities, called robots, have to rearrange themselves in such a way a…
Universal Systems of Oblivious Mobile Robots
Paola Flocchini, Nicola Santoro, Giovanni Viglietta +1
An oblivious mobile robot is a stateless computational entity located in a spatial universe, capable of moving in that universe. When activated, the robot observes the universe and…