P-Path Minimum Distance Connectivity from Head Quarter to the Cities

Revathi P; Suresh Babu C; Purusotham S; Sundara Murthy M

doi:10.24297/ijmit.v4i2.4625

Authors

Revathi P Research Scholar, Dept. of Mathematics, S. V. University, Tirupati, Andhra Pradesh, India.
Suresh Babu C Academic Consultant, Dept. of Mathematics, S. V. University, Tirupati, Andhra Pradesh, India.
Purusotham S Asst. Professor, Statistics and OR Division,VIT University, Vellore, Tamil Nadu, India
Sundara Murthy M Professor, Dept. of Mathematics, S. V. University, Tirupati, Andhra Pradesh, India.

DOI:

https://doi.org/10.24297/ijmit.v4i2.4625

Keywords:

Lexi Search Algorithm, Pattern Recognition Technique, Partial word, Pattern, Mathematical formation.

Abstract

Many Combinatorial programming problems are NP-hard (Non Linear Polynomial), and we consider one of them called P path minimum distance connectivity from head quarter to the cities. Let there be n cities and the distance matrix D(i, j, k) is
given from i
th
city to j
th
city using k
th
facility. There can be an individual factor which influences the distances/cost and that
factor is represented as a facility k. We consider m<n cities are in cluster and to connect all the cities in subgroup (cluster)
from others by using same facility k. The problem is to find minimum distance to connect all the cities from head quarter
(say 1) threw p-paths subject to the above considerations. For this problem we developed a Pattern Recognition
Technique based Lexi Search Algorithm, we programmed the proposed algorithm using C. we compared with the existed
models and conclude that it suggested for solving the higher dimensional problems.

Downloads

Download data is not yet available.

References

[1]. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, B. Chazelle, Journal ACM 47
(2000), 1028-1047. Prelim. version in FOCS 1997.
[2]. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, ISBN 0-7167-1045-5.
[3]. Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum
spanning trees", Journal of the Association for Computing Machinery 42 (2): 321â€“328,
doi:10.1145/201019.201022, MR 1409738
[4]. Pettie, Seth; Ramachandran, Vijaya (2002), "A randomized time-work optimal parallel algorithm for finding a
minimum spanning forest", SIAM Journal on Computing 31 (6): 1879â€“1895, doi:10.1137/S0097539700371065,
MR 1954882.
[5]. Pettie, Seth; Ramachandran, Vijaya (2002), "Minimizing randomness in minimum spanning tree, parallel
connectivity, and set maxima algorithms", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02),
San Francisco, California, pp. 713â€“722.
[6]. Pop, P.C.,â€New models of the Generalized Minimum Spanning Tree Problemâ€, Journal of Mathematical Modelling
and Algorithms, Volume 3, issue 2, 2004, 153-166.
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
1 2 3 4 5 6 7
Series2
Series1
ISSN 2278-5612
294 | P a g e J u l y , 2 0 1 3
[7]. Reeves, C.R., â€œModeren Metaheuristics Techniques for Combinatorial Problemsâ€, Blackwell, Oxford, 1993.
[8]. Sobhan Babu, K., Chandra Kala, K., Purusotham, S. and Sundara Murthy, M. â€œA New Approach for Variant Multi
Assignment Problemâ€, International Journal on Computer Science and Engineering, Vol.02,No.5, 2010, 1633-1640.
[9]. Sundara Murthy, M. â€œCombinatorial Programming: A Pattern Recognition Approach,â€ A Ph.D. Thesis, REC,
Warangal. 1979.
[10]. Suresh Babu C, Sobhan Babu K and Sundara Murthy M, 2011, published a paper entitled â€œVariant Minimum
Spanning Network Connectivity Problemâ€ by the International Journal of Engineering Science and Technology for
publication. Volume 3, No. 1, Jan-Feb 2012.