Search

A set of vertices S is a resolving set in a graph if each vertex has a unique array of distances to the vertices of S. The natural problem of finding the smallest cardinality of a resolving set in a graph has been widely studied over the years. In this paper, we wish to resolve a set of vertices (up to ź vertices) instead of just one vertex with the aid of the array of distances. The smallest cardinality of a set S resolving at most ź vertices is called ź-set-metric dimension. We study the problem of the ź-set-metric dimension in two infinite classes of graphs, namely, the two dimensional grid graphs and the n-dimensional binary hypercubes. We introduce a way to locate several intruders instead of only one of a resolving set.This prevents mistakes in the location procedure, see Example 2(i).New geometric approach compared to the usual resolving sets (Section 2).We give the complete and optimal results for the two dimensional grid graphs.Optimal results for a very high number of intruders in binary hypercubes.

Let G=(V,E) be a connected graph on n vertices. The proximity@p(G) of G is the minimum average distance from a vertex of G to all others. The eccentricitye(v) of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity ecc(G) of the graph G is 1n@?"v"@?"V"("G")e(v). Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on n>=3 vertices, ecc(G)-@p(G)=

Let R and B be two sets of distinct points such that the points of R are coloured red and the points of B are coloured blue. Let G be a family of planar graphs such that for each graph in the family |R| vertices are red and |B| vertices are blue. The set R@?B is a universal point set for G if every graph G@?G has a straight-line planar drawing such that the blue vertices of G are mapped to the points of B and the red vertices of G are mapped to the points of R. In this paper we describe universal point sets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem.

We study sets of points in the two-dimensional Euclidean plane. The relative neighbourhood graph (RNG) of a point set is a straight line graph that connects two points from the point set if and only if there is no other point in the set that is closer to both points than they are to each other. A triangulation of a point set is a maximal set of nonintersecting line segments (called edges) with vertices in the point set. We introduce angular restrictions in the triangulations. Using the well-known method of exclusion regions, we show that the relative neighbourhood graph is a part of every triangulation all of the angles of which are greater than or equal to 30^o.

For a positive integer c, a c-vertex-ranking of a graph G = (V,E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a c-vertex-ranking of a given graph using the minimum number of ranks. In this paper we give an optimal parallel algorithm for solving the c-vertex-ranking problem on trees in O(log2n) time using linear number of operations on the EREW PRAM model.

For a nontrivial graph G(V,E) , the distance d(u,v) between vertices u and v is the length of a shortest path p(u,v) in G if such a path exists. The eccentricity e(u) of a vertex u in a graph is the distance from u to a vertex furthest from u . That is, e(u)= max {d(u,v)∣v∈V} . The radius of a graph G is defined as min {e(u)∣u∈V} . A center of G is a vertex whose eccentricity is equal to the radius. The center problem is to find all centers of a graph. In this paper, we shall study the center problem on weighted cactus graphs, and develop an optimal algorithm.

We investigate the optimal covering of vertices by Hamming balls of radius t in a hypercube Z2n such that any vertex in Z2n can be uniquely identified by examining the vertices that cover it. Given Z2n and an integer t ⩾ 1, we find a (minimal) set C of vertices such that every vertex in Z2n belongs to a unique set of balls of radius t centered at the vertices in C . This is useful in diagnosing processor faults in hypercube-based multiprocessor systems.

A hub set in a graph G is a set U@?V(G) such that any two vertices outside U are connected by a path whose internal vertices lie in U. We prove that h(G)=h"c(G)>=4 are obtained by substituting graphs into three consecutive vertices of a cycle; this yields a polynomial-time algorithm to check whether h"c(G)=@c"c(G).

In this paper, we study the bounded fan-out m-center problem. Given a graph G = (V, E), positive integers m and B, the problem is to find the location of m centers to service all the vertices so as to minimize the maximum service radius subject to the constraint that each center is allowed to service no more than B vertices. Note that the centers can be located either on a vertex or an edge. It is well known that the m-center problem without fan-out bound (B = ∞) is NP-complete for general graphs, Euclidean geometry, and rectilinear metric geometry. The same is also true for the bounded fan-out m-center problem. In this paper, we present an O(n log2 n · log m) algorithm for tree networks, where n is the number of vertices.

If the distance of any two vertices becomes longer after a vertex u is removed, then u is called a hinge vertex. The fault of a hinge vertex will increase the overall communication cost in a network. Therefore, finding the set of all hinge vertices in a graph can be used to identify critical nodes in a real network. We shall propose a linear time algorithm for finding all hinge vertices of a permutation graph.

We newly define a generalized vertex-ranking of a graph G as follows: for a positive integer c, a c-vertex-ranking of G is a labeling (ranking) of the vertices of C with integers such that, for any label i, every connected component of the graph obtained from G by deleting the vertices with label > i has at most c vertices with label i. Clearly an ordinary vertex-ranking is a l-vertex-ranking and vice-versa. We present an algorithm to find a c-vertex-ranking of a given tree T using the minimum number of ranks in time O(cn) where n is the number of vertices in T.

We present an O(⨍V⨍ + ⨍E⨍) algorithm for finding the minimum cost between two vertices of a Manhattan graph (V, E) - a graph in which the vertices are points in Z d and the weight on each edge is the Manhattan distance between its two incident vertices.

An O(m)-algorithm for computing the average distance of an interval graph with m edges of unit length is presented. A slight modification of the algorithm can be used for computing the average distance of a tree with weighted edges in time O(n), where n is the number of vertices.

A graph is said to be of bandwidth 2 if its vertices can be laid out linearly such that the maximum distance between vertices adjacent in the graph does not exceed 2. The bandwidth concept has applications to VLSI layout, matrix processing, memory management for data structures, and more. We develop a constructive, simple, linear-time algorithm for deciding whether a given biconnected graph is of bandwidth 2.

The problem considered here is to find, for all vertices v in a given tree T , the maximum among the distances from v to all other vertices in T . We show that this problem can be solved in O(log n ) time using O( n /log n ) processors on an EREW PRAM, where n is the number of vertices in the tree. The correctness of the algorithm relies on two simple but interesting properties of trees. We then show an application of the result.

Given a graph and a positive integer k, the Separation Problem is to find a linear layout for the vertices such that each pair of adjacent vertices has a distance of at least k in the layout. A polynomial time algorithm has been studied earlier for the special case when the graph is a directed forest. In this paper, we study the problem when the roots of the trees in the forest have different constraints on their earliest starting positions. We present an O(n log n) algorithm for the problem with n vertices in the forest. We then use the algorithm to schedule real-time jobs with minimum distance constraints.

We present a simple linear time algorithm for finding a cycle through three fixed vertices in an undirected graph. The algorithm is based on decompositions into triconnected components and on a combinatorial result of Lovász.

Given a graph, G = (V, E), and sets S ⊂ V and Q ⊂ V, the maximal paths problem requires the computation of a maximal set of vertex disjoint paths in G that begin at vertices of S and end at vertices of Q. It is well known that this problem can be solved sequentially in time that is proportional to the number of edges in G. However, its parallel complexity is not known. This note shows that this problem is NC-reducible to that of computing a depth-first search forest in a suitable n-vertex graph. This result can also be extended to directed graphs.

We present a new polynomial-time heuristic algorithm for finding a solution to the Travelling Salesman Problem (TSP) for any complete and edge-weighted graph K n , with a set of vertices V and a set of edges E where | V | = n . In a few words, this method is based on the idea of linking the elements of V progressively, one by one, in such a way that the vertex selection which produces fewest disturbances to the other vertices not yet connected, will be selected as the next vertex to join to the subset of already connected vertices. When the cost of the result is compared to the cost of the best circuit, it appears that a good sub-solution is obtained in most of the cases tested. Moreover, comparison tests made between the heuristic introduced and the well-known Quick method, produce a better behaviour, for almost every case, in the first approach.