China
Africa
Explore chapters and articles related to this topic
Orienteering and Coverage
Published in Yasmina Bestaoui Sebbane, Multi-UAV Planning and Task Allocation, 2020
The first step in Algorithm 24 is to calculate the degree of each vertex. If all the vertices have even degree, then the algorithm finds an Euler tour using the end-pairing technique. If any vertices have odd degree, a minimum weighted matching among the odd degree vertices is found using all pairs’ shortest-path graph of the odd vertices. Because the matching algorithm requires a complete graph, all pairs’ shortest-path algorithm is a way to optimally connect all the odd vertices. The matching finds the minimum cost set of edges that connect the odd nodes. Finally, the algorithm finds a tour on the new Eulerian graph. The end-pairing technique is used to generate the Eulerian cycle from the graph, consisting of two steps: First, it builds cycles that intersect at least one vertex.Next, the cycles are merged together two at a time by adding one cycle onto another at the intersecting vertex.
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
A Euler tour in a directed graph is a closed tour along the arcs such that each arc is traversed exactly once, even though some nodes may be traversed multiple times. Given a directed graph, the Euler tour problem seeks such a tour. The aircraft maintenance routing problem where maintenance is always carried out overnight can be modeled as a Euler tour problem. To do so, each node should model an airport and each arc a daily route for a single aircraft, linking its starting airport to its ending airport. Among all airports, some can conduct overnight maintenance checks. When a Euler tour exists, all aircraft can repeatedly experience the same sequence of daily routes though in any given day, they are all assigned to different daily routes.
How to encrypt a graph
Published in International Journal of Parallel, Emergent and Distributed Systems, 2020
Suppose then that graph is stored in the cloud, encrypted as . In this case, some queries can be performed by legitimate users on the encrypted data without decrypting them. Only when the reply to the query is received, does the legitimate user who knows the encryption/decryption key K obtain the plaintext. Examples of such queries include straightforward ones, such as ‘What is the weight of the edge ?’, as well as more complex ones such as ‘Find the weight of a simple path between and that goes through a given set of vertices’, and ‘Find the weight of a spanning tree (or that of an Euler tour, or a Hamilton cycle) over a given set of vertices’. Whether the encrypted weight of one edge is returned (as in the first query), or a sequence of edges and their encrypted weights are returned (as in the second and third queries), the true weights are obtained using K. Similarly, queries that involve finding neighbourhoods or connected entities, as in social networks, can easily be handled in the same way.