Search

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. [ABSTRACT FROM AUTHOR]

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 FROM AUTHOR]

Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite Wolbachia of its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the phenomenon. We consider in this paper the quantitative Lock-Key model which currently represents a good hypothesis that is consistent with the data available. CI is in this case modelled as the problem of covering the edges of a bipartite graph with the minimum number of chain subgraphs. This problem is already known to be NP-hard, and we provide an exponential algorithm with a non trivial complexity. It is frequent that depending on the dataset, there may be many optimal solutions which can be biologically quite different among them. To rely on a single optimal solution may therefore be problematic. To this purpose, we address the problem of enumerating (listing) all minimal chain subgraph covers of a bipartite graph and show that it can be solved in quasi-polynomial time. Interestingly, in order to solve the above problems, we considered also the problem of enumerating all the maximal chain subgraphs of a bipartite graph and improved on the current results in the literature for the latter. Finally, to demonstrate the usefulness of our methods we show an application on a real dataset. [ABSTRACT FROM AUTHOR]

We introduce a hybrid metaphor for the visualization of the reconciliations of co-phylogenetic trees, that are mappings among the nodes of two trees with constraints on the leaves. The typical application is the visualization of the co-evolution of hosts and parasites in biology. Our strategy combines a space-filling and a node-link approach. Differently from traditional methods, it guarantees an unambiguous and downward representation whenever the reconciliation is time-consistent (i.e., biologically-feasible). We address the problem of the minimization of the number of crossings in the representation, by giving a characterization of planar instances and by establishing the complexity of the problem. Finally, we propose heuristics for computing representations with few crossings. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers d m i n and d m a x , d m i n ≤ d m a x , 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 d m i n ≤ d T (u , v) ≤ d m a x , where d T (u , v) is the sum of the weights of the edges on the unique path P T (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 P 2 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 C 8 2). [ABSTRACT FROM AUTHOR]

Abstract A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected subgraph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an analogous result for the case when the input graph is a maximal outerplanar graph. [ABSTRACT FROM AUTHOR]

This paper deals with the well known classes of threshold and difference graphs, both characterized by separators , i.e. node weight functions and thresholds. We design an efficient algorithm to find the minimum separator, and we show how to maintain minimum its value when the input (threshold or difference) graph is fully dynamic, i.e. edges/nodes are inserted/removed. Moreover, exploiting the data structure used for maintaining the minimality of the separator, we study the disjoint union and the join of two threshold graphs, showing that the resulting graphs are threshold signed graphs, i.e. a superclass of both threshold and difference graphs. Finally, we consider the complement operation on all the three introduced classes of graphs. All these operations produce in output the modified graph in terms of their separator and require time linear w.r.t. the number of different degrees. We observe that recomputing from scratch the separator would run either in linear (for threshold and difference graphs) or quadratic (for threshold signed graphs) time w.r.t. the number of nodes of the graph. [ABSTRACT FROM AUTHOR]

A graph G = (V,E) is a pairwise compatibility graph (PCG) if there exists an edgeweighted 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. [ABSTRACT FROM AUTHOR]

Given a graph and two positive integers j and k, an -edge-labeling is a function f assigning to edges of E colors from a set such that if e and e′ are adjacent, i.e. they share a common endpoint, if e and e′ are not adjacent and there exists an edge adjacent to both e and e′. The aim of the -edge-labeling problem consists of finding a coloring function f such that the value of is minimum. This minimum value is called . This problem has already been studied on hexagonal, squared and triangular grids, but mostly not coinciding upper and lower bounds on have been proposed. In this paper we close some of these gaps or find better bounds on in the special cases and . Moreover, we propose tight -edge-labelings for eight-regular grids. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The Dilworth number of a graph is the size of the largest subset of its nodes in which the close neighborhood of no node contains the neighborhood of another one. In this paper we give a new characterization of Dilworth k graphs, for each value of k, exactly defining their structure. Moreover, we put these graphs in relation with pairwise compatibility graphs (PCGs), i.e. graphs on n nodes that can be generated from an edge-weighted tree T that has n leaves, each representing a different node of the graph; two nodes are adjacent in the graph if and only if the weighted distance between the corresponding leaves in T is contained between two given non-negative real numbers, m and M. When either m or M are not used to eliminate edges from G, the two subclasses leaf power and minimum leaf power graphs (LPGs and mLPGs, respectively) are defined. Here we prove that graphs that are either LPGs or mLPGs of trees obtained connecting the centers of k stars with a path are Dilworth k graphs, and the opposite is true when k=1,2, but not when k≥3. Finally, we show that the relations we proved between Dilworth k graphs and chains of k stars hold only for LPGs and mLPGs, but not for PCGs. [ABSTRACT FROM AUTHOR]

The Dilworth number of a graph is the size of the largest subset of its nodes in which the close neighborhood of no node contains the neighborhood of another one. In this paper we give a new characterization of Dilworth k graphs, for each value of k, exactly defining their structure. Moreover, we put these graphs in relation with pairwise compatibility graphs (PCGs), i.e. graphs on n nodes that can be generated from an edge-weighted tree T that has n leaves, each representing a different node of the graph; two nodes are adjacent in the graph if and only if the weighted distance between the corresponding leaves in T is contained between two given non-negative real numbers, m and M. When either m or M are not used to eliminate edges from G, the two subclasses leaf power and minimum leaf power graphs (LPGs and mLPGs, respectively) are defined. Here we prove that graphs that are either LPGs or mLPGs of trees obtained connecting the centers of k stars with a path are Dilworth k graphs, and the opposite is true when k=1,2, but not when k≥3. Finally, we show that the relations we proved between Dilworth k graphs and chains of k stars hold only for LPGs and mLPGs, but not for PCGs. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A graph C is called a pairwise compatibility graph (PCG) if there exists a positive edge weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a node u ∈ V and there is an edge (u, v) ∈ E if and only if dmin, ≦ dT(lu,lv) < dmax, where dT(1u,1v) is the sum of the weights of the edges on the unique path from 1u to lv, in T. In this paper we study the relations between the pairwise compatibility property and superciasses of threshold graphs, i.e., graphs where the neighborhoods of any couple of nodes either coincide or are included one into the other. Namely, we prove that some of these superclasses belong to the FCC class. Moreover, we tackle the problem of characterizing the class of graphs that are PCGs of a star, deducing that also these graphs are a generalization of threshold graphs. [ABSTRACT FROM 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 . [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: The -labeling problem consists of assigning colors from the integer set to the nodes of a graph in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize and it is in general NP-complete. In this paper the problem of -labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a -approximate algorithm for -labeling unigraphs is designed. This algorithm runs in time, improving the time of the algorithm based on the greedy technique, requiring time, that may be near to for unigraphs. [Copyright &y& Elsevier]

The use of mobile sensors is of great relevance to monitor critical areas where sensors cannot be deployed manually. The presence of data collector sinks causes increased energy depletion in their proximity, due to the higher relay load under multi-hop communication schemes (sink-hole phenomenon). We propose a new approach towards the solution of this problem by means of an autonomous deployment algorithm that guarantees the adaptation of the sensor density to the sink proximity and enables their selective activation. The proposed algorithm also permits a fault tolerant and self-healing deployment, and allows the realization of an integrated solution for deployment, dynamic relocation and selective sensor activation. We formally prove the termination of our algorithm. Performance comparisons between our proposal and previous approaches show how the former can efficiently reach a deployment at the desired variable density with moderate energy consumption under a wide range of operative settings. [ABSTRACT FROM AUTHOR]

Mobile sensor networks are important for several strategic applications devoted to monitoring critical areas. In such hostile scenarios, sensors cannot be deployed manually and are either sent from a safe location or dropped from an aircraft. Mobile devices permit a dynamic deployment reconfiguration that improves the coverage in terms of completeness and uniformity. In this paper we propose a distributed algorithm for the autonomous deployment of mobile sensors called Push & Pull. According to our proposal, movement decisions are made by each sensor on the basis of locally available information and do not require any prior knowledge of the operating conditions or any manual tuning of key parameters. We formally prove that, when a sufficient number of sensors are available, our approach guarantees a complete and uniform coverage. Furthermore, we demonstrate that the algorithm execution always terminates preventing movement oscillations. Numerous simulations show that our algorithm reaches a complete coverage within reasonable time with moderate energy consumption, even when the target area has irregular shapes. Performance comparisons between Push & Pull and one of the most acknowledged algorithms show how the former one can efficiently reach a more uniform and complete coverage under a wide range of working scenarios. [ABSTRACT FROM AUTHOR]

Abstract: The antibandwidth problem is to label vertices of a -vertex graph injectively by , so that the minimum difference between labels of adjacent vertices is maximised. The problem is motivated by the obnoxious facility location problem, radiocolouring, work and game scheduling and is dual to the well known bandwidth problem. We prove exact results for the antibandwidth of complete -ary trees, even, and estimate the parameter for odd up to the second order term. This extends previous results for complete binary trees. [Copyright &y& Elsevier]

Abstract: The Minimum-Energy Broadcast problem is to assign a transmission range to every station of an ad hoc wireless networks so that (i) a given source station is allowed to perform broadcast operations and (ii) the overall energy consumption of the range assignment is minimized. We prove a nearly tight asymptotical bound on the optimal cost for the Minimum-Energy Broadcast problem on square grids. We also derive near-tight bounds for the Bounded-Hop version of this problem. Our results imply that the best-known heuristic, the MST-based one, for the Minimum-Energy Broadcast problem is far to achieve optimal solutions (even) on very regular, well-spread instances: its worst-case approximation ratio is about and it yields hops, where is the number of stations. As a by product, we get nearly tight bounds for the Minimum-Disk Cover problem and for its restriction in which the allowed disks must have non-constant radius. Finally, we emphasize that our upper bounds are obtained via polynomial time constructions. [Copyright &y& Elsevier]

Abstract: This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In our problem, channels assigned to adjacent vertices must be at least 2 apart, while channels assigned to vertices at distance 2 must be different. An exact linear time algorithm is provided for the class of threshold graphs. For matrogenic and matroidal graphs approximate algorithms are given. Consequently, previously known results concerning subclasses of cographs, split graphs and graphs with diameter 2 are improved. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is an integer labeling of vertices of , such that adjacent vertices have labels which differ by at least , and vertices at distance two have labels which differ by at least . The span of an -labeling is the difference between the largest and the smallest label. We investigate -labelings of trees of maximum degree , seeking those with small span. Given , and , span is optimal for the class of trees of maximum degree , if is the smallest integer such that every tree of maximum degree has an -labeling with span at most . For all parameters , such that , we construct -labelings with optimal span. We also establish optimal span of -labelings for stars of arbitrary degree and all values of and . [Copyright &y& Elsevier]

The L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h, k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h, k)-labeling problem has been intensively studied in some special cases, i.e. when k = 0 (vertex coloring), h = k (vertex coloring the square of the graph) and h = 2k (radio- or λ -coloring) but no results are known in the general case for regular grids. In this paper, we completely solve the L(h, k)-labeling problem on cellular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds. For the sake of completeness, we study also hexagonal and squared grids. [ABSTRACT FROM AUTHOR]

The L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h, k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h, k)-labeling problem has been intensively studied in some special cases, i.e. when k = 0 (vertex coloring), h = k (vertex coloring the square of the graph) and h = 2k (radio- or λ -coloring) but no results are known in the general case for regular grids. In this paper, we completely solve the L(h, k)-labeling problem on cellular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds. For the sake of completeness, we study also hexagonal and squared grids. [ABSTRACT FROM AUTHOR]

L(h,1)-labeling, h=0,1,2, is a class of coloring problems arising from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least h apart while nodes connected by a two long path must receive different colors. This problem is NP-complete even when limited to planar graphs. Here, we focus on L(h,1)-labeling restricted to regular tilings of the plane and to outerplanar graphs. We give a unique parametric algorithm labeling each regular tiling of the plane. For these networks, a channel can be assigned to any node in constant time, provided that relative positions of the node in the network is locally known. Regarding outerplanar graphs with maximum degree Δ, we improve the best known upper bounds from Δ+9, Δ+5 and Δ+3 to Δ+3, Δ+1 and Δ colors for the values of h equal to 2, 1 and 0, respectively, for sufficiently large values of Δ. For h=0,1 this result proves the polinomiality of the problem for outerplanar graphs. Finally, we study the special case Δ=3, achieving surprising results. [Copyright &y& Elsevier]

In this paper we study the topological equivalence problem of multistage interconnection networks (MINs). We prove a new characterization of topologically equivalent MINs by means of a novel approach. Applying this characterization to log N stage MINs we completely describe the equivalence class which the Reverse Baseline belongs to. Most important, we apply the characterization to (2 log N−1) stage MINs obtained as concatenation of two log N stage Reverse Baseline equivalent MINs: in this way, we deduce an O(N log N) time algorithm testing the equivalence of two such MINs. This result substantially improves the time complexity of the previously known algorithms (O(N4 log N)). Finally, we determine the number of different equivalence classes of (2 log N−1) stage MINs and we characterize each of them. [Copyright &y& Elsevier]

In this paper we propose compact routing schemes having space and time complexities comparable to a 2-interval routing scheme for the class of networks decomposable as layered cross product (LCP) of rooted trees. As a consequence, we are able to design a “quasi” 2-interval routing scheme (i.e. a 2-interval routing scheme plus a fast and small local algorithm) for butterflies, meshes of trees and fat trees. Then we show that a compact routing scheme for general networks which are LCP of cyclic graphs cannot be found by any method using only information about shortest paths on the factors. Nevertheless, we extend our scheme to Benesˇ networks, although they cannot be decomposed as the LCP of trees. [Copyright &y& Elsevier]

The edge-bandwidth problem is an analog of the classical bandwidth problem, in which one has to label the edges of a graph by distinct integers such that the maximum difference of labels of any two incident edges is minimized. We prove tight bounds on the edge-bandwidth of hypercube and butterfly graphs, and complete k-ary trees which extends and improves on previous known results. [Copyright &y& Elsevier]

Presents a cost-efficient parallel algorithm that produces an orthagonal grid drawing. Definition of orthagonal grid drawing; Basic techniques used by the algorithm; Use of standard graph-theoretic terminology of the design and analysis of computer algorithms; Usefulness of cubic graphs for modeling a number of real-life situations in computer graphics, digital geometry and visualization.

In this paper we deal with the layout of Trivalent Cayley Interconnection Networks. Namely, we prove that a lower bound on their layout area is Ω(2[SUPn-1] × 2[SUPn-1]) and we exhibit some methods to lay these networks out in O(2[SUPn-1] × 2[SUPn-1]). We point out that these layout methods work for other networks decomposable into equal length cycles connected by following fixed rules. [ABSTRACT FROM AUTHOR]

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 \beta r(v)^2, where \beta >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 \Theta (\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 \sqrtn 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. [ABSTRACT FROM AUTHOR]