82 research outputs found
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
The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography
No full textGiven 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
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
On the Domination Number of t-Constrained de Bruijn Graphs (Short Paper)
No full textMotivated by the work on the domination number of de Bruijn graphs and some of its generalizations, we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely t-constrained de Bruijn graphs, where t is a positive integer, and then study the domination number of these graphs. Within the definition of t-constrained de Bruijn graphs, de Bruijn and Kautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs, respectively. This generalization inherits many structural properties of de Bruijn graphs and may have similar applications in interconnection networks or bioinformatics. We establish upper and lower bounds for the domination number on t-constrained de Bruijn graphs both in the directed and in the undirected case. These bounds are often very close and in some cases we are able to find the exact value
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
(Eternal) Vertex Cover Number of Infinite and Finite Grid Graphs (short paper)
No full textIn 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
On the approximability of the L(h, k)-labelling problem on bipartite graphs (Extended abstract)
No full textGiven an undirected graph G, an L(h, k)-labelling of G assigns colors to vertices from the integer set {0,.. lambda(h,k)}, such that any two vertices v(i) and v(j) receive colors c(v(i)) and c(v(j)) satisfying the following conditions: i) if v(i) and v(j) are adjacent then vertical bar c(v(i)) - c(v(j))vertical bar >= h; ii) if v(i) and v(j) are at distance two then vertical bar c(v(i)) - c(v(j))vertical bar >= k. The aim of the L(h, k)-labelling problem is to minimize lambda(h,k)- In this paper we study the approximability of the L(h,k)-labelling problem on bipartite graphs and extend the results to s-partite and general graphs. Indeed, the decision version of this problem is known to be DIP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the L(h,k)-labelling problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an L(h, k)-labelling for the input bipartite graph. We derive an approximation algorithm with performance ratio bounded by (4)/D-3(2), where, D is equal to the minimum even value bounding the minimum of the maximum degrees of the two partitions. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension d, i.e. the maximum edge cardinality, with performance ratio d. Furthermore, we consider a different approximation technique based on the reduction of the L(h, k)-labelling problem to the vertex-coloring of the square of a graph. Using this approach we derive an approximation algorithm with performance ratio bounded by min(h, 2k)root n + o(k root n), assuming h >= k. Hence, the first technique is competitive when D O(n(1/4)) These algorithms match with a result in [2] stating that L(1,1) labelling n-vertex bipartite graphs is hard to approximate within(n1/2-)epsilon, for any epsilon > 0, unless NP=ZPP. We then extend the latter approximation strategy to s-partite graphs, obtaining a (min(h, sk)root n + o(sk root n))-approximation ratio, and to general graphs deriving an (h root n + o(h root n))-approximation algorithm, assuming h >= k. Finally, we prove that the L(h, k)-labelling problem is not easier than coloring the square of a graph
Pairwise Compatibility Graphs of Caterpillars
No full textA 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 of V and there is an edge (u, v) in 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 pairwise compatibility graph admits a full binary tree as witness tree T
Corrigendum to “On Pairwise Compatibility Graphs having Dilworth Number Two”
No full textIn [4] we put in relation graphs with Dilworth number at most two and the two classes LPG and mLPG. In order to prove this relation, we have heavily exploited a result we deduced from [1]. We have now realized that this result is not always true, so in this corrigendum we correctly restate the result concerning the relation between graphs with Dilworth number at most two and the two classes of LPG and mLPG
- …
