Solving Combinatorial Optimization Problems using Distributed Approach
|
10.5120/4380-6060 |
Sunita Choudhary and G N Purohit. Article: Solving Combinatorial Optimization Problems using Distributed Approach. International Journal of Computer Applications 35(3):13-17, December 2011. Full text available. BibTeX
@article{key:article,
author = {Sunita Choudhary and G.N. Purohit},
title = {Article: Solving Combinatorial Optimization Problems using Distributed Approach},
journal = {International Journal of Computer Applications},
year = {2011},
volume = {35},
number = {3},
pages = {13-17},
month = {December},
note = {Full text available}
}
Abstract
Combinatorial optimization is a way of finding an optimum solution from a finite set of objects. For combinatorial optimization problems, the number of possible solutions grows exponentially with the number of objects. These problems belong to the class of NP hard problems for which probably efficient algorithm does not exist. Using the distributed approach with parallelization these problems can be solved with a good bound. We show that how the concept of distributed algorithm can help in solving graph colouring problem i.e. one of the NP complete problem.
References
- Brelaz, D. "New Methods to Color the Vertices of a Graph." Comm. ACM 22, 251-256, 1979.
- Blum A. “New approximation algorithms for graph coloring”. Journal of the ACM, 31(3):470–516,1994.
- Björklund A., Husfeldt T., and Koivisto M, "Set Partitioning via Inclusion-Exclusion", presented at SIAM J. Comput., 2009, pp.546-563.
- Dhawan and S.K. Prasad, "Taming the exponential state space of the maximum lifetime sensor cover problem", in Proc. HiPC, 2009, pp.170-178
- Applegate, D.; Bixby, R.; Chvatal, V.; and Cook, W. "Finding Cuts in the TSP (a Preliminary Report)." Technical Report 95-05, DIMACS. Piscataway NJ: Rutgers University, 1995
- Johnson, D. S. (1979), "Worst case behavior of graph coloring algorithms", Proc. 5th Southeastern Conf. Combinatorics, Graph Theory and Computation, Winnipeg: Utilitas Mathematica, pp. 513–527
- Kuhn, F., Moscibroda, T., Wattenhofer, R.: “What cannot be computed locally!” In: Proc. of the 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp.300-309
- Lawler E.L., “A note on the complexity of the chromatic number problem”, Information Processing Lett., 5 (1976), pp. 66-67.
- Michael R. Garey and David S. Johnson, “Computer and Intractability: A Guide to the theory of NP- Completeness”, W.H. Freeman & Co., New York, NY, USA, 1979
- Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics,11, Springer-Verlag, pp. 65–84
- Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal 10 (1): 85–86,