1,720,990 research outputs found
Some Problems Related to the Space of Optimal Tree Reconciliations (Invited Talk)
No full textTree reconciliation is a general framework for investigating the evolution of strongly dependent systems as hosts and parasites or genes and species, based on their phylogenetic information. Indeed, informally speaking, it reconciles any differences between two phylogenetic trees by means of biological events. Tree reconciliation is usually computed according to the parsimony principle, that is, to each evolutionary event a cost is assigned and the goal is to find tree reconciliations of minimum total cost. Unfortunately, the number of optimal reconciliations is usually huge and many biological applications require to enumerate and to examine all of them, so it is necessary to handle them. In this paper we list some problems connected with the management of such a big space of tree reconciliations and, for each of them, discuss some known solutions
A Realistic Model for Rescue Operations after an Earthquake
No full textWhen a natural disaster occurs, emergency responders need information and real-time imagery in order to make better decisions and save time. Unmanned aerial vehicles (UAVs) used by emergency services, such as police officers or firefighters, can rapidly provide situational awareness over a large area, reducing the time and number of researchers required to locate and rescue people, thus reducing the costs and risks of search and rescue missions. This work considers the problem of completely overfly an area just affected by an earthquake with the objective of opportunely direct rescue teams. It provides a complete model that tries to keep into account all the main real-life issues in two different realistic scenarios
Pairwise compatibility graphs: A survey
No full textA graph G = (V, E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two nonnegative real numbers dmin and dmax such that each leaf u of T is a node of V and there is an edge (u, v) ∈ E if and only if dmin ≤ dT (u, v) ≤ dmax, where dT (u, v) is the sum of weights of the edges on the unique path from u to v in T. In this article, we survey the state of the art concerning this class of graphs and some of its subclasses
(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs (short paper)
Full text linkIn 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 neighbor vertices. The eternal vertex cover problem consists in determining the minimum number of necessary guards. Motivated by previous literature, in this paper, we study the vertex cover and eternal vertex cover problems on regular grids when passing from the infinite to the finite version 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 and minimum eternal vertex covers in order to be well-defined for infinite grids
A Matheuristic for Multi-Depot Multi-Trip Vehicle Routing Problems
No full textStarting from a real-life application, in this short paper, we propose the original Multi-Depot Multi-Trip Vehicle Routing Problem with Total Completion Times minimization (MDMT-VRP-TCT). For it, we propose a mathematical formulation as a MILP, design a matheuristic framework to quickly solve it, and experimentally test its performance. It is worth noting that this problem is original as in the literature its characteristics (i.e., multi-depot, multi-trip and total completion time) can be found separately, but never all together. Moreover, regardless of the application, our solution works in any case in which a multi-depot multi-trip vehicle routing problem must be solved
Autonomous data detection and inspection with a fleet of UAVs
Full text linkConsider an area of interest A , where a set of n sites lie. Two kinds of information can be captured from each site: light and heavy information. A fleet of m homogeneous UAVs, each one equipped with a battery B , is available at a common depot, where the flight mission of each UAV starts and finishes. The problem we consider focuses on a single flight of the fleet of UAVs and aims at collecting their light information from all sites (that can be retrieved, not necessarily passing over each site, but simply "close"to it). At the same time, the fleet will have to select a limited number of sites from which to collect their heavy information. Flying among sites and acquiring information from them (both light and heavy) has a battery cost. On the other hand, a profit is associated with the action of acquiring heavy information from a site. We refer to the extraction of light and heavy information from a site as to weakly or strongly cover the site. The aim of the problem consists of retrieving light information from all sites while maximizing the overall profit, keeping the battery consumption of each UAV within B . In this paper, we model this real -life situation as a new combinatorial optimization problem that we call m3DIP, for which we provide a mixed integer programming model. Given the high degree of complexity of the problem, in this way we are not able to provide a solution in a reasonable time. To address larger instances we propose a matheuristic in which we exploit a path -based algorithm filled with only a subset of feasible cycles (paths) provided by different heuristics. The output indicates which path to select and the set of nodes to be strongly and weakly covered by each trip. We compare our matheuristic with the results obtained by every single heuristic on a large set of instances, showing that the matheuristic strongly outperforms them. An interesting insight is that even paths provided by a heuristic with very bad performances can be useful if combined with paths provided by other heuristics and if the coverage decisions are reoptimized by the matheuristic. We also show the benefit of adding fictitious additional points that UAVs can visit to weakly cover a subset of sites, without actually visiting none of them
A Realistic Model to Support Rescue Operations after an Earthquake via UAVs
Full text linkIn this paper, we consider the problem of completely flying over an area just hit by an earthquake with a fleet of Unmanned Aerial Vehicles (UAVs) to opportunely direct rescue teams. The cooperation between UAVs ensures that the search for possible survivors can be faster and more effective than the solutions currently implemented by civil protection. To study this scenario, we introduce the Cover by Multitrips with Priorities (CMP) problem, which tries to keep into account all the main real-life issues connected to the flight and coordination of the UAVs. We conduct a theoretical study to estimate the best number of UAVs and additional batteries, to give indications to the organization that leads the rescue teams to be able to guarantee rapid and effective rescue. Finally, based on some theoretical considerations, we propose some heuristics that tackle the problem of flying over the whole area with a fleet of UAVs in the shortest possible time. Simulations show that they work efficiently in both the proposed scenarios and provide better performance than previous solutions once they are arranged to work in our scenarios. The main advantages of our approach w.r.t. the current drone-based solutions used by the civil defense are that UAVs do not need drivers so the time of all available rescue workers can be invested in doing something else. In our model, we take into account that some sites (e.g. buildings with a high fire risk or schools and hospitals) have a higher priority and must be inspected first, and the possibility that UAVs can make a decision based on what they detect. Finally, our approach allows UAVs to collaborate so that the same sites will be flown over exactly once in order to speed up the rescue mission
Some classes of graphs that are not PCGs
Full text linkA graph G=(V,E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax, dmin≤dmax, such that each node u∈V is uniquely associated to a leaf of T and there is an edge (u,v)∈E if and only if dmin≤dT(u,v)≤dmax, where dT(u,v) is the sum of the weights of the edges on the unique path PT(u,v) from u to v in T. Understanding which graph classes lie inside and which ones outside the PCG class is an important issue. In this paper we show that some interesting classes of graphs have empty intersection with PCG; they are wheels, strong product of a cycle and P2 and the square of an n node cycle, with n sufficiently large. As a side effect, we show that the smallest planar graph not to be PCG has not 20 nodes, as previously known, but only 8 (it is C82)
- …
