PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Contemporary Methods for Graph Coloring as an Example of Discrete Optimization

Autorzy
Treść / Zawartość
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
This paper provides an insight into graph coloring application of the contemporary heuristic methods. It discusses a variety of algorithmic solutions for The Graph Coloring Problem (GCP) and makes recommendations for implementation. The GCP is the NP-hard problem, which aims at finding the minimum number of colors for vertices in such a way, that none of two adjacent vertices are marked with the same color.With the advent of multicore processing technology, the metaheuristic approach to solving GCP reemerged as means of discrete optimization. To explain the phenomenon of these methods, the author makes a thorough survey of AI-based algorithms for GCP, while pointing out the main differences between all these techniques.
Słowa kluczowe
Twórcy
  • University of Social Sciences, Sienkiewicza 9, 90-113 Lodz, Poland
Bibliografia
  • [1] D. Zuckerman, ”Linear degree extractors and the inapproximability of Max Clique and Chromatic Number”, in Proc. STOC06, Seattle, 2006, pp. 681-690.
  • [2] T.R. Jensen and B. Toft ,”Graph Coloring Problems”, New York, Wiley, 1995.
  • [3] K. Appel and W. Haken, ”Every planar graph is four colorable. Pt. I: Discharging”, Illinois Journal of Mathematics, vol. 21, pp. 429-490, 1977.
  • [4] I. Holyer, ”The NP-completeness of edge-coloring”, SIAM Journal on Computing, vol. 10, no. 4, pp. 718720, 1981.
  • [5] G. Chartrand and P. Zhang, ”Chromatic Graph Theory”, Chapman and Hall, 2009.
  • [6] V.G. Vizing, ”On an estimate of the chromatic class of a p-graph”, Diskret. Analiz, no. 3, pp. 25-30, 1964.
  • [7] P.G. Tait, ”On the coloring of maps”, in Proc. Royal Soc. Edinburgh Sec. A, vol. 10, pp. 501-503, 1878-1880.
  • [8] J. Mycielski, ”On the coloring of graphs”, Coll. Math, vol. 3, pp. 161-162, 1955.
  • [9] M.M. Halldorsson, ”A still better performance guarantee for approximate graph coloring”, Inf. Process. Lett., vol. 45, pp. 19-23, 1993.
  • [10] D. Brelaz, ”New methods to color the vertices of a graph”, Communications of the ACM, vol. 22, pp. 251-256, 1979.
  • [11] W. Arbaugh, S. Banerjee and A. Mishra, ”Weighted Coloring Based Channel Assignment for WLAN’s”, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, issue 3, pp. 19-31, 2005.
  • [12] M. Kubale, ”Optymalizacja dyskretna. Modele i metody kolorwania grafow”, (in polish), Warszawa, WNT, 2002.
  • [13] P. Furmanowicz and K. Tanas, ”A survey of graph coloring - its types, methods and applications”, Foundation of Computing and Decision Sciences, vol. 37, no. 3, pp. 223-238, 2012.
  • [14] V. Yegnanarayanan, ”Graph colourings and partitions”, Theoretical Computer Science, vol. 263, pp. 59-79, 2001.
  • [15] K. Schnabel, ”Representation of graphs by integers”, in Topics in Combinatorics and Graph Theory, Physica-Verlag HD, Heidelberg, 1990.
  • [16] R.C. Entringer, D.E. Jackson and D.A. Smyder, ”Distance in graphs”, Czechoslovak Math. J., vol. 26, no. 101, pp. 283296, 1976.
  • [17] I. Tomescu and A.M. Robert, ”On distances in chromatic graphs”, Quart. J. Math., vol. 40, issue 4, pp. 475480, 1 Dec. 1989
  • [18] R. Dorne and J.K. Hao, ”Tabu search for graph coloring, T-coloring and set T-coloring”, in Metaheuristics: Theory and Applications, Kluwer Academic Publishers, 1997.
  • [19] D. Szyfelbein, ”Genetic algorithms for graph coloring”, in Proc. 4th Conference Neural Networks and Their Applications, pp. 605-610, 1999.
  • [20] X. Zhu, ”Star Chromatic number and products of graphs”, Journal of Graph Theory, vol. 16, issue 6, pp. 557-569, Dec. 1992.
  • [21] X. Zhu, ”Circular chromatic number and graph minors”, Taiwanese Journal of Mathematics, vol. 4, no. 4, pp. 643-660, Dec. 2000
  • [22] X. Zhu, ”On the chromatic number of the products of hypergraphs”, Ars Combinatoria, vol. 34, pp. 25-31, Jan. 1992.
  • [23] F. Hermann and A. Hertz, ”Finding the chromatic number by means of critical graphs”, ACM Journal of Experimental Algorithmics, vol. 7, pp. 1-9, 2002.
  • [24] I. Mendez-Diaz and P. Zabala, ”A branch-and-cut algorithm for graph coloring”, Discrete Applied Mathematics, vol. 154, pp. 826-847, 2006.
  • [25] D. de Werra and D. Kobler, ”Graph coloring problems”, in Paradigms of Combinatorial Optimization, ISTE-Wiley, pp. 265-310, 2010.
  • [26] D.J. Welsh and M.B. Powell, ”An upper bound for the chromatic number of a graph and its application to timetabling problem”, Comp. J., vol. 10, no. 1, pp. 85-86, 1967.
  • [27] D.W. Matula, G. Marble and J.D. Isaacson, ”Graph coloring algorithms”, in Graph Theory of and Computing, Academic Press, New York, pp. 109-122, 1972.
  • [28] D. Brelaz, ”New methods to color the vertices of a graph”, Communications of the ACM, vol. 22, pp. 251-256, 1979.
  • [29] D.S. Johnson, ”Worst case behavior of graph coloring algorithms”, in Proc. 5th Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica Publishing, Winnipeg, pp. 513-527, 1974.
  • [30] G. Lewandowski and A. Condon, ”Experiments with Parallel Graph Coloring Heuristics and Applications of Graph Coloring”, Technical Report, 1994.
  • [31] F.T. Leighton, ”A graph coloring algorithm for large scheduling problems”, Journal of Research of the National Bureau of Standards, vol. 84, no. 6, pp. 489-506, 1979.
  • [32] S. Kirkpatrick, Jr.C.D. Gelatt and M.P. Vecchi, ”Optimization by Simulated Annealing”, Science, vol. 220, pp. 671-680, 1983.
  • [33] F. Glover, ”Tabu Search: A Tutorial”, Interfaces, vol. 20, no. 4, pp. 74-94, 1990.
  • [34] J.H. Holland, ”Adaptation in Natural and Artificial Systems”, University of Michigan Press, Ann Arbor, MI, 1975.
  • [35] J.J. Hopfield and D.W. Tank, ”Neural Computation of Decisions in Optimization Problems”, Biological Cybernetics, vol. 52, issue 3, pp. 141-152, July 1985.
  • [36] W.H. Press, S.A. Teukolsky, W.T. Vetterling and B.P. Flannery, ”Numerical Recipes in C”, in Numerical Recipes 3rd Edition: The Art of Scientific Computing, Cambridge University Press, 2007.
  • [37] D. Costa and A. Hertz , ”Ants can color graphs”, Journal of the Operational Research Society, vol. 48, no. 3, pp. 295-305, March 1997.
  • [38] F. Glover, ”Tabu Search - Part 2”, ORSA Journal on Computing, vol. 2, no. 1, pp.432, 1990.
  • [39] D.E. Goldberg, ”Genetic Algorithms”, Dorling Kindersley Pvt Ltd, 2008.
  • [40] A. DiBlas, A. Jagota and R. Hughey, ”Energy function-based approaches to graph coloring”, Transactions on Neural Networks, vol 13, no. 1, pp. 81-91, 2002.
  • [41] D.W. Gassen and J.D. Carothers, ”Graph color minimization using neural networks”, in Proceedings of the IEEE International Conference on Neural Networks, pp. 1541-1544, 1993.
  • [42] M.O. Berger, ”k-coloring vertices using a neural network with convergence to valid solutions”, in Proceedings of the IEEE International Conference on Neural Networks, vol. 7, pp. 4515-4517, 1994.
  • [43] A. DiBlas, A. Jagota and R. Hughey, ”Optimization neural networks on SIMD parallel computers”, Parallel Computing, vol. 31, no. 1, pp. 97-115, 2005.
  • [44] A. Jagota, ”An adaptive, multiple restarts neural network algorithm for graph coloring”, European Journal of Operational Research, vol. 91, pp. 257-270, 1996.
  • [45] A. Jagota, ”Scheduling problems in radio networks using Hopfield networks”, in Proceedings of the International Workshop on Applications of Neural Networks to Telecommunications, Lawrence Erlbaun Associates, Hillsdale, NY, pp. 67-76, 1993.
  • [46] A. Fiat and G.J. Woeginger, ”Online Algorithms The State of the Art”, Lecture Notes in Computer Science, Berlin, Springer, 1998.
  • [47] M.M. Hall, ”Frugal Methods for the Independent Set and Graph Coloring Problems”, PhD. thesis, The State University of New Jersey, New Brunswick, New Jersey, October 1991.
  • [48] A. Gyarfas and J. Lehel, ”First-Fit and on-line chromatic number of families of graphs”, Ars Combinatoria, pp. 168-176, 1990.
  • [49] M. Duque-Anton, D. Kunz and B. Ruber, ”Channel assignment for cellular radio using simulated annealing”, in IEEE Trans. Vehicular Technology, vol. 42, pp. 1421, 1993.
  • [50] G. Wang and N. Ansari, ”Optimal broadcast scheduling in packet radio networks using mean field annealing”, in IEEE Journal on Selected Areas in Communications, vol. 15, no. 2, pp. 250260, 1997.
  • [51] D. Zhaoa, L. Luo and K. Zhang, ”An improved ant colony optimization for the communication network routing problem”, Mathematical and Computer Modelling, vol. 52, pp. 19761981, 2010.
  • [52] C.H. Chen and C.J. Ting, ”An improved ant system algorithm for routing problem”, Journal of the Chinese Institute of Industrial Engineers, vol. 23, no. 2, pp. 115126, 2006.
  • [53] J. Xu, S.Y. Chiu and F. Glover, ”Tabu search for dynamic routing communications network design”, Telecommunication Systems, vol. 8, issue 1, pp. 55-77, 1997.
  • [54] J. Xu, S.Y. Chiu and F. Glover, ”Probabilistic tabu search for telecommunications network design”, Combinatorial Optimization: Theory and Practice, vol. 1, no. 1, pp. 69-94, 1996.
  • [55] T. Edwards, D.S.W. Tansley, R.J. Frank and N. Davey, ”Traffic Trends Analysis Using Neural Networks”, in Proceedings of International Workshop on Applications of Neural Networks to Telecommunications, pp. 157-164, 1997.
  • [56] J. Yeo, H. Lee, and S. Kim, ”An efficient broadcast scheduling algorithm for TDMA ad hoc networks”, Computers and Operations Research, vol. 29, pp. 17931806, 2002.
  • [57] M. Javedankherad and Z. Zeinalpour-Yazdi, ”Content Placement in Cache Networks Using Graph-Coloring”, 2017.
  • [58] A.S. Sairam, S. Roy and R. Sahay, Coloring networks for attacker identification and response, Security Comm. Networks, vol. 8, 751-768, 2015.
  • [59] D. S. Johnson, C. R. Aragon, L. A. McGeoch, C. Schevon, ”Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning”, Operations Research, Vol. 39, No. 3, May-June 1991, pp. 378-406.
Uwagi
Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-b4152d30-7b07-490c-b0c9-13b275b39f8a
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.