CFP last date
22 April 2024
Reseach Article

Solving Combinatorial Optimization Problems using Distributed Approach

by Sunita Choudhary, G.N. Purohit
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 35 - Number 3
Year of Publication: 2011
Authors: Sunita Choudhary, G.N. Purohit
10.5120/4380-6060

Sunita Choudhary, G.N. Purohit . Solving Combinatorial Optimization Problems using Distributed Approach. International Journal of Computer Applications. 35, 3 ( December 2011), 13-17. DOI=10.5120/4380-6060

@article{ 10.5120/4380-6060,
author = { Sunita Choudhary, G.N. Purohit },
title = { Solving Combinatorial Optimization Problems using Distributed Approach },
journal = { International Journal of Computer Applications },
issue_date = { December 2011 },
volume = { 35 },
number = { 3 },
month = { December },
year = { 2011 },
issn = { 0975-8887 },
pages = { 13-17 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume35/number3/4380-6060/ },
doi = { 10.5120/4380-6060 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:21:02.192354+05:30
%A Sunita Choudhary
%A G.N. Purohit
%T Solving Combinatorial Optimization Problems using Distributed Approach
%J International Journal of Computer Applications
%@ 0975-8887
%V 35
%N 3
%P 13-17
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Brelaz, D. "New Methods to Color the Vertices of a Graph." Comm. ACM 22, 251-256, 1979.
  2. Blum A. “New approximation algorithms for graph coloring”. Journal of the ACM, 31(3):470–516,1994.
  3. Björklund A., Husfeldt T., and Koivisto M, "Set Partitioning via Inclusion-Exclusion", presented at SIAM J. Comput., 2009, pp.546-563.
  4. Dhawan and S.K. Prasad, "Taming the exponential state space of the maximum lifetime sensor cover problem", in Proc. HiPC, 2009, pp.170-178
  5. 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
  6. 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
  7. 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
  8. Lawler E.L., “A note on the complexity of the chromatic number problem”, Information Processing Lett., 5 (1976), pp. 66-67.
  9. 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
  10. 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
  11. 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,
Index Terms

Computer Science
Information Sciences

Keywords

Combinatorial Optimization NP Complete Graph Coloring Distributed Computing