Given a graph G = ( V , E ) , an L (3, 2, 1)-labeling of G consists of assigning an integer label from { 0 , … , σ ( G ) } to each node v such that it is at least 3 apart from the labels of the nodes adjacent to v , at least 2 apart from the labels of the nodes at distance 2 from v , and different from the labels of the nodes at a distance 3 from v . The L (3, 2, 1)-labeling problem consists of determining the minimum value of σ ( G ) for which such labeling exists; this number is denoted by λ ( G ) and is called the L (3, 2, 1)-labeling number of G . The problem has many possible applications in coding theory, signal processing, radar, data base management, communication network addressing, etc. and is NP-hard in general, while, it has been proved to be polynomially solvable for some classes of graphs. In this paper, we continue the study of the L (3, 2, 1)-number of the square of cycles C n 2 , either closing or reducing the gap between the upper and lower bounds on the values of λ ( C n 2 ) when n assumes several values. To prove our bounds, we introduce the new notions of labeling schemes associated with sets of consecutive labels and of forbidden labeling schemes.

BACKGROUND: Cophylogeny reconciliation is a powerful method for analyzing host-symbiont coevolution. The cophylogeny problem consists of mapping the phylogenetic tree of the symbionts into the one of the hosts, including events such as duplications, co-speciation, host-switches, and extinctions by comparing the discrepancies between the topologies of the associated symbiont evolutionary trees. Visualizing tree reconciliations is important for biologists as it aids in understanding and identifying specific patterns in the coevolution of hosts and symbionts. Additionally, when multiple optimal solutions exist, it allows for the quick comparison of different reconciliations between the same pair of trees. RESULTS: Here, we present VIRI (visual inspector of reconciliation instances), a new tree reconciliation visualizer. We adopt a hybrid metaphor combining space-filling (for host trees) and node-link (for symbiont trees) approaches, implementing the algorithms described in Calamoneri et al. (Theor Comput Sci 815:228-245. https://doi.org/10.1016/j.tcs.2019.12.024 , 2020). The visualizations produced by VIRI are designed to be clear and interpretable, thanks to an unambiguous, top-down layout of tree reconciliations and the preservation of the user's mental map when comparing multiple reconciliations on the same pair of trees. In particular, the consistent use of a shared host tree layout across visualizations is a novel feature that facilitates direct comparison. Moreover, VIRI proposes a crossing-free visualization whenever possible. Finally, VIRI allows users to store datasets and download their visualizations, offering a convenient way to organize and share data. An example of visualization produced by VIRI is depicted in Fig. 1. CONCLUSIONS: VIRI efficiently produces clear and easy-to-read visualizations of tree reconciliations. VIRI is free and available at https://viri.di.uniroma1.it/ .

A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k , then we call the graph a k -interval-PCG; in symbols, G = k -interval-PCG ( T , I 1 ,…, I k ). It is known that 2-interval-PCGs do not contain all graphs, and the smallest known graph outside this class has 135 nodes. Here, we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.

In the eternal vertex cover problem, mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on its edges by moving to neighboring vertices. The eternal vertex cover problem consists of determining the minimum number of necessary guards. Motivated by previous literature, we study the vertex cover and eternal vertex cover problems on regular grids when passing from infinite to finite versions of the same graphs, and we provide either coinciding or very tight lower and upper bounds on the number of necessary guards. To this aim, we generalize the notions of minimum vertex covers and minimum eternal vertex cover in order to be well-defined for infinite grids.

One of the most valuable and promising applications for Unmanned aerial vehicles (UAVs) is in natural disaster management, where these aircraft can operate autonomously without any need for human intervention during their flights. In this paper, we foster the interface of Operational Research with computer science in general and sensor networking in particular by focusing on managing a post-disaster emergency scenario where the use of a fleet of UAVs helps rescue teams identify people needing help inside an affected area. We model this situation as an original graph theoretical problem called Multi-Depot Multi-Trip Vehicle Routing Problem with Total Completion Time minimization (MDMT-VRP-TCT). The main novelty of the MDMT-VRP-TCT is the combination of the following three features: multi-depot, multi-trip, and completion time minimization. We propose a mixed-integer linear programming (MILP) formulation, develop a matheuristic framework to address large instances, and present an extended set of experiments to test the performance of the proposed matheuristic: first, we compare the matheuristic with the MILP formulation on a set of small instances (up to 30 nodes); then, we compare our matheuristic with two heuristics from networking literature, showing that it outperforms the existing algorithms.

Abstract In this paper, we consider the problem of flying over an area affected by a natural disaster (e.g. an earthquake) with a fleet of self-piloting unmanned aerial vehicles with cameras or other kinds of sensors on board; the aim is to acquire knowledge of the situation before rescuers start working. We model this situation as a new graph theoretical problem; then, we study its complexity providing an approximation ratio that becomes constant in some special (though practically reasonable) cases; finally, we put in relation the approximability of this new problem and of a well-known one. To the best of our knowledge, no previous work has ever considered all together the constraints we take into account from a theoretical point of view, so this is the first very general graph theoretical model for this problem.

Tree reconciliation is a general framework for investigating the mutual influence between gene and species trees according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find a reconciliation of minimum total cost. The resulting optimization problem is known as the reconciliation problem. Usually, the considered events are: co-divergence, gene Duplication, horizontal gene Transfer, and gene Loss (DTL model), while in a more conservative setting, gene transfers are not allowed (DL model). The reconciliation problem requires, in the DL model, time linear in the dimension of the two trees and at least quadratic time in the DTL model. Hence, it is reasonable to argue that the introduction of horizontal gene transfers increases the complexity of the problem. Instead, we introduce horizontal gene transfers with some constraints and prove that the problem is still linear in the dimension of the trees. Namely, we allow gene transfers of length bounded by k=2, on the basis of the observation that transfers are more likely to occur between closely related species than between distantly related ones. Then we extend the same reasonings to the case in which under additional constrains. In this paper we study also another problem related to the reconciliation one, that is optimally rooting one of the two trees when it is not, and also for it we prove similar results. The relevance of this contribution lies in showing that, in the transit from the DL to the DTL model, the computational time does not increase suddenly to quadratic but remains linear in the case when gene transfers are very short (i.e., happening between very close genes).

In this article, we address the problem of autonomously deploying mobile sensors in an unknown complex environment. In such a scenario, mobile sensors may encounter obstacles or environmental sources of noise, so that movement and sensing capabilities can be significantly altered and become anisotropic. Any reduction of device capabilities cannot be known prior to their actual deployment, nor can it be predicted. We propose a new algorithm for autonomous sensor movements and positioning, called DOMINO (DeplOyment of MobIle Networks with Obstacles). Unlike traditional approaches, DOMINO explicitly addresses these issues by realizing a grid-based deployment throughout the Area of Interest (AoI) and subsequently refining it to cover the target area more precisely in the regions where devices experience reduced sensing. We demonstrate the capability of DOMINO to entirely cover the AoI in a finite time. We also give bounds on the number of sensors necessary to cover an AoI with asperities. Simulations show that DOMINO provides a fast deployment with precise movements and no oscillations, with moderate energy consumption. Furthermore, DOMINO provides better performance than previous solutions in all the operative settings.

A graph G=(V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n=7, …, 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any PCG admits a full binary tree as witness tree T.

A graph G is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular, all these graphs except for the wheel on seven vertices W7 are PCGs of a particular structure of a tree: a centipede.

-

In order to prolong the lifetime of a wireless sensor network (WSN) devoted to monitoring an area of interest, a useful means is to exploit network redundancy, activating only the sensors that are strictly necessary for coverage and making them work with the minimum necessary sensing radius. In this article, we introduce the first algorithm that reduces sensor coverage redundancy through joint Sensor Activation and sensing Radius Adaptation (SARA) in general application scenarios comprising two classes of devices: sensors with variable sensing radius and sensors with fixed sensing radius. This device heterogeneity is explicitly addressed by modeling the coverage problem through Voronoi-Laguerre diagrams that, differently from Voronoi diagrams, allow for correctly identifying each sensor coverage region depending on the sensor current radius and the radii of its neighboring nodes. SARA executes quickly with guaranteed termination and, given the currently available nodes, it always guarantees maximum coverage. By means of extensive simulations, we show that SARA obtains remarkable improvements with respect to previous solutions, ensuring, in networks with heterogeneous nodes, longer network lifetime and wider coverage.

Given any fixed non-negative integer values h and k, the L(h, k)-labelling problem consists in an assignment of non-negative integers to the nodes of a graph such that adjacent nodes receive values which differ by at least h, and nodes connected by a 2-length path receive values which differ by at least k. The span of an L(h, k)-labelling is the difference between the largest and the smallest assigned frequency. The goal of the problem is to find out an L(h, k)-labelling with a minimum span. The L(h, k)-labelling problem has intensively been studied following many approaches and restricted to many special cases, concerning both the values of h and k and the considered classes of graphs. This paper reviews the results from previously published literature, looking at the problem with a graph algorithmic approach. It is an update of a previous survey written by the same author.

The L(2, 1)-labeling of a digraph G is a function f from the node set of G to the set of all non-negative integers such that |f(x)−f(y)| ≥ 2 if x and y are at distance 1, and f(x) ≠ f(y) if x and y are at distance 2, where the distance from node x to node y is the length of a shortest dipath from x to y. The minimum over all L(2, 1)-labeling of G of the largest used label is called ⁠. In this paper, we study the L(2, 1)-labelings problem on squared, triangular and hexagonal grids and for them we compute the exact values of ⁠.

In this paper, we address the problem of deploying heterogeneous mobile sensors over a target area. Traditional approaches to mobile sensor deployment are specifically designed for homogeneous networks. Nevertheless, network and device homogeneity is an unrealistic assumption in most practical scenarios, and previous approaches fail when adopted in heterogeneous operative settings. For this reason, we introduce VorLag, a generalization of the Voronoi-based approach which exploits the Laguerre geometry. We theoretically prove the appropriateness of our proposal to the management of heterogeneous networks. In addition, we demonstrate that VorLag can be extended to deal with dynamically generated events or uneven energy depletion due to communications. Finally, by means of simulations, we show that VorLag provides a very stable sensor behavior, with fast and guaranteed termination and moderate energy consumption. We also show that VorLag performs better than its traditional counterpart and other methods based on virtual forces.

We consider static ad hoc wireless networks whose nodes, equipped with the same initial battery charge, may dynamically change their transmission range. When a node v transmits with range r(v), its battery charge is decreased by β r(v)2, where β > 0 is a fixed constant. The goal is to provide a range assignment schedule that maximizes the number of broadcast operations from a given source (this number is denoted by the length of the schedule). This maximization problem, denoted by Max LifeTime, is known to be NP-hard and the best algorithm yields worst-case approximation ratio Θ (log n), where n is the number of nodes of the network. We consider random geometric instances formed by selecting n points independently and uniformly at random from a square of side length √n in the euclidean plane. We present an efficient algorithm that constructs a range assignment schedule having length not smaller than 1/12 of the optimum with high probability. Then we design an efficient distributed version of the above algorithm, where nodes initially know n and their own position only. The resulting schedule guarantees the same approximation ratio achieved by the centralized version, thus, obtaining the first distributed algorithm having provably good performance for this problem.

In this paper we propose GREASE, a distributed algorithm to deploy mobile sensors in an unknown environment with obstacles and field asperities that may cause sensing anisotropies and non uniform device capabilities. These aspects are not taken into account by traditional approaches to the problem of mobile sensor self-deployment. GREASE works by realizing a grid-shaped deployment throughout the Area of Interest (AoI) and adaptively refining the grid to find new sensor positions to cover the target area more precisely in the zones where devices experience reduced movement, sensing and communication capabilities. We give bounds on the number of sensors necessary to cover an AoI with obstacles and noisy zones. Simulations show that GREASE provides a fast deployment with precise movements and no oscillations, with moderate energy consumption.

In this paper we address the problem of deploying heterogeneous mobile sensors over a target area. We show how traditional approaches designed for homogeneous networks fail when adopted in the heterogeneous operative setting.

Abstract Given two nonnegative integers h and k, an L(h, k)‐labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)‐labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)‐labeling problem is NP‐complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co‐comparability graphs, its subclass of interval graphs, and circular‐arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)‐labeling of co‐comparability and circular‐arc graphs. In particular, we provide the first algorithm to L(h, k)‐label co‐comparability, interval, and circular‐arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously‐known ones using a number of colors that is at most twice the optimum. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

The Min Energy Broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the energy cost) yielded by the range assignment. Min Energy Broadcast is known to be NP-hard. We consider random-grid networks where nodes are chosen independently at random from the n points of a √n x √n square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform.

Given any fixed non-negative integer values h and k, the L(h, k)-labelling problem consists in an assignment of non-negative integers to the nodes of a graph such that adjacent nodes receive values which differ by at least h, and nodes connected by a 2 length path receive values which differ by at least k. The span of an L(h, k)-labelling is the difference between the largest and the smallest assigned frequency. The goal of the problem is to find out an L(h, k)-labelling with minimum span. The L(h, k)-labelling problem has been intensively studied following many approaches and restricted to many special cases, concerning both the values of h and k and the considered classes of graphs. This paper reviews the results from previous by published literature, looking at the problem with a graph algorithmic approach.

Abstract In this article we consider the three‐dimensional layout of hypercube networks. Namely, we study the problem of laying hypercube networks out on the three‐dimensional grid with the properties that all nodes are represented as rectangular slices and lie on two opposite sides of the bounding box of the layout volume. We present both a lower bound and a layout method, providing an upper bound on the layout volume and the maximum wire‐length of the hypercube network. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 1–8 2006

The main contribution of this work is to offer a simple and cost-efficient parallel algorithm that, given an arbitrary n-vertex cubic graph G as input, produces an orthogonal grid drawing of G in O(log n) time, using n processors on an EREW PRAM. Our algorithm matches the time and cost performance of the best previously-known algorithm while at the same time improving the constant factors involved in two important metrics: layout area and number of bends. More importantly, however, our algorithm stands out by its conceptual simplicity and ease of implementation.

We establish upper and lower bounds on the layout area of the butterfly network, which differ only in low-order terms. Specifically, the N-input, N-output butterfly network can be laid out in area (1 + o(1)) N^2, while no layout of the network can have area smaller than (1 - o(1)) N^2. These results improve both the known upper bound and the known lower bound on the area of butterfly network layouts.