On some interconnections between combinatorial optimization and extremal graph theory

Authors

  • Dragoš M. Cvetković Faculty of Electrical Engineering, University of Belgrade, Belgrade, Serbia and Montenegro
  • Pierre Hansen GERAD and École des Hautes Études Commerciales, Montréal HT A, Canada
  • Vera V. Kovačević-Vujčić Faculty of Organizational Sciences, University of Belgrade, Belgrade, Serbia and Montenegro

DOI:

https://doi.org/10.2298/YJOR0402147C

Keywords:

combinatorial optimization, extremal graph theory, variable neighborhood search, mathematical programming.

Abstract

The uniting feature of combinatorial optimization and extremal graph theory is that in both areas one should find extrema of a function defined in most cases on a finite set. While in combinatorial optimization the point is in developing efficient algorithms and heuristics for solving specified types of problems, the extremal graph theory deals with finding bounds for various graph invariants under some constraints and with constructing extremal graphs. We analyze by examples some interconnections and interactions of the two theories and propose some conclusions.

References

Aouchiche, M., Caporossi, G., Hansen, P. (2001) Variable neighborhood search for extremal graphs. 8: Variations on Graffiti 105. Congressus Numerantium, 148, 129-144

Balister, P., Bollobas, B., Riordan, O., Schelp, R.H. (2003) Graphs with large maximum degree containing no odd cycles of a given length. Journal of Combinatorial Theory Series B, 87, 2, 366-373

Bollobas, B. (1978) Extremal graph theory. New York-San Diego, itd: Academic Press

Bollobas, B. (1995) Extremal graph theory. u: Graham R.L., M. Grötschel, L. Lovász [ur.] Handbook of combinatorics, Amsterdam, itd: Elsevier, I, II, 1231-1292

Caporossi, G., Cvetković, D., Gutman, I., Hansen, P. (1999) Variable neighborhood search for extremal graphs. 2: Finding graphs with extremal energy. J Chem Inf Comput Sci, 39, 984-996

Caporossi, G., Gutman, I., Hansen, P. (1999) Variable neighborhood search for extremal graphs. 4: Chemical tress with extremal connectivity index. Comput Chem, 23, 469-477

Caporossi, G., Hansen, P. (2000) Variable neighborhood search for extremal graphs. 1: The AutoGraphiX system. Discrete Mathematics, 212, 2, 29-44

Caporossi, G., Hansen, P. (2004) Variable neighborhood search for extremal graphs. 5: Three ways to automate finding conjectures. Discrete Mathematics, 276, 3, 81-94

Cvetković, D., Simić, S.K. (1994) Graph theoretical results obtained by the support of the expert system 'Graph'. Bull. Acad. Serbe Sci. Arts Cl. Sci. Math. Natur., Sci. Math, 107, br. 19, 19-41

Cvetković, D.M., Simić, S.K., Caporossi, G., Hansen, P. (2001) Variable neighborhood search for extremal graphs 3. On the largest eigenvalue of color-constrained trees. Linear & Multilinear Algebra, vol. 49, br. 2, str. 143-160

Cvetković, D.M., Čangalović, M.M., Kovačević-Vujčić, V.V. (1999) Semi definite programming methods for the symmetric traveling salesman problem. u: Cornnejols G.R., E. Burkard, G. J. Woeginger [ur.] Integer Programming and Combinatorial Optimization, Proc. 7th Int. IPCO Conf., Graz, Austria, June, Lecture Notes Comp. Sci. 1610, Berlin, itd: Springer Verlag, 126-136

Fowler, P.W., Hansen, P., Caporossi, G., Sondini, A. (2001) Variable neighborhood search for extremal graphs. 7. Polyenes with maximum HOMO-LUMO gap. Chemical Physics Letters, 49, 143-146

Gerber, M.U., Hansen, P., Hertz, A. (2002) Extension of Tur'an's theorem to the 2-stability number. Graphs and Combinatorics, 18, 3, 479-489

Gutman, I., Hansen, P., Melot, H. (2005) Variable neighborhood search for extremal graphs. 10. Comparison of irregularity indices for chemical trees. Journal of Chemical Information and Modeling, vol. 45, br. 2, str. 222-230

Hansen, P., Melot, H. (2003) Variable neighborhood search for extremal graphs. 6: Analyzing bounds for the connectivity index. J Chem Inf Comput Sci, 43(1): 1-14

Hansen, P., Melot, H. (2000) Variable neighborhood search for extremal graphs. 9. Bounding irregularity of a graph. to appear

Hansen, P., Mladenović, N.M. (2001) Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130, 449-467

Lovasz, L., Pelikan, J. (1973) On the eigenvalues of trees. Periodica Mathematica Hungarica, 3, 175-182

Mckay, B.D. (1998) Isomorph-free exhaustive generation. Journal of Algorithms, 26, 2, 306-324

Mckay, B.D. (1990) Nauty user's guide, version 1.5. Canberra: Australian National University - Department of Computer Science, Technical Report, TR-CS-90-02

Mladenović, N.M., Hansen, P. (1997) Variable neighborhood search. Computers and Operations Research, 24, 11, 1097-1100

Petrović, R., Guberinić, S., Batanović, V., Cvetković, D. (1995) Operational research models in action, the result of international cooperation - A potpourri. European journal of operational research, 87(3): 500-506

Turan, P. (1941) Eine Extremalaufgabe aus der Graphentheorie. Fiz. Mat. Lapok, 48, 436-452

Downloads

Published

2004-09-01

Issue

Vol. 14 No. 2 (2004)

Section

Research Articles

License

Copyright (c) YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.