Header menu link for other important links
X
Landmarks in binary tree derived architectures
P. Manuel, B. Rajan, , M. Chris Monica
Published in
2011
Volume: 99
   
Pages: 473 - 486
Abstract
Let M = {v1,v2 ... vl) be an ordered set of vertices in a graph G. Then (d(u,v1),d(u,v2) ... d(u,vl)) is called the M-location of a vertex u of G. The set M is called a locating set if the vertices of G have distinct M-locations. A minimum locating set is a set M with minimum cardinality. The cardinality of a minimum locating set of G is called Location Number L(G). This concept has wide applications in motion planning and in the field of robotics. In this paper we consider networks with binary tree as an underlying structure and determine minimum locating set of such architectures.We show that the location number of an n-level X-tree lies between 2n-3 and 2n-3 + 2. We further prove that the location number of an N × N mesh of trees is greater than or equal to N/2 and less than or equal to N.}, references={Liestman, A.L., Shermer, T.C., Degree-constrained network spanners with non constant delay (1995) SIAM Journal on Discrete Math, 8 (2), pp. 291-321; Rajan, B., Rajasingh, I., Cynthia, J.A., Manuel, P., (2003) On Minimum Metric Dimension, the Indonesia-Japan Conference on Combinatorial Geometry and Graph Theory, , Bandung, Indonesia, September; Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W. H. Freeman and Company; Chartrand, G., Eroh, L., Johnson, M.A., Oellermann, O.R., Resolvability in Graphs and the Metric Dimension of a Graph (2000) Discrete Applied Mathematics, 105, pp. 99-113; Goodman, J.R., Carlo, H.S., Hypertree: A multiprocessor interconnection topology (1981) IEEE Transactions on Computers, C-30 (12), pp. 923-933; Haynes, T.W., (1998) Stephen Hedetniemi and Peter Slater, Fundamentals of Domination in Graphs, , CRC Press; 1 edition; Harary, F., Melter, R.A., (1976) The Metric Dimension of A Graph, pp. 191-195. , Ars Combinatorica; Hsu, W.J., Page, C.V., Embedding Mesh in a Large Family of Graphs (1992) Parallel Processing Letters, 2 (2-3), pp. 149-155; Khuller, S., Ragavachari, B., Rosenfeld, A., Landmarks in graphs (1996) Discrete Applied Mathematics, 70, pp. 217-229; Leighton, F.T., (1992) Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, , Morgan Kaufmann Publishers, San Mateo, California; Melter, R.A., Tomcscu, I., Metric bases in digital geometry, computer vision (1984) Graphics and Image Processing, 25, pp. 113-121; Manuel, P., Rajan, B., Rajasingh, I., Cynthia, J.A., (2005) On Minimum Metric Dimension of de Bruijn Graph, pp. 40-45. , Proc. National Conference on Computational Intelligence, India, March; Manuel, P., Rajan, B., Rajasingh, I., Chris Monica, M., Landmarks in torus networks (2006) Journal of Discrete Mathematical Sciences & Cryptography, 9 (2), pp. 263-271; Manuel, P.D., Abd-El-Barr, M.I., Rajasingh, I., Rajan, B., An Efficient Representation of Benes Networks and its Applications (2008) Journal of Discrete Algorithm, 6 (1), pp. 11-19; Manuel, P., Rajan, B., Rajasingh, I., Chris Monica, M., On minimum metric dimension of honeycomb networks (2008) Journal of Discrete Algorithm, 6 (1), pp. 20-27; Slater, P.J., (1975) Leaves of Trees, Congr. Numer., 14, pp. 549-559; Slater, P.J., Dominating and Reference Sets in a Graph (1988) J. Math. Phys. Sci., 22, pp. 445-455}, correspondence_address1={Manuel, P.; Department of Information Science, , 13060, Kuwait}, issn={03817032}, language={English}, abbrev_source_title={Ars Comb.}, document_type={Article}, source={Scopus},
About the journal
JournalArs Combinatoria