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., and Hansen, P., “Variable Neighborhood Search for extremal graphs, 8. Variations on Graffiti 105”, Cong. Numer., 148 (2001) 129-144.

Balister, P., Bollobás, B., Riordan, O., and Schelp, R.H., “Graphs with large maximum degree containing no odd cycles of a given length”, J. Combin. Theory Ser. B, 87 (2) (2003) 366-373.

Bollobás, B., Extremal Graph Theory, Academic Press, London-New York-San Francisco, 1978.

Bollobás, B., “Extremal graph theory”, in: R.L. Graham, M. Grötschel, L. Lovász (eds.), Handbook of Combinatorics I, II, Elsevier-Amsterdam, MIT Press-Cambridge, MA, 1995, 1231-1292.

Caporossi, G., Cvetković, D., Gutman, I., and Hansen, P., “Variable Neighborhood Search for extremal graphs, 2. Finding graphs with extremal energy”, J. Chem. Inf. Comp. Sci., 39 (1999) 984-996.

Caporossi, G., Gutman, I., and Hansen, P., “Variable Neighborhood Search for extremal graphs, 4. Chemical trees with extremal connectivity index”, Comput. Chem., 23 (1999) 469-477.

Caporossi, G., and Hansen, P., “Variable Neighborhood Search for extremal graphs I”, Discrete Math., 212 (2000) 29-44.

Caporossi, G., and Hansen, P., “Variable Neighborhood Search for extremal graphs, 5. Three ways to automate finding conjectures”, Discrete Math., 276 (2004) 81-94.

Cvetković, D., Čangalović, M., and Kovačević-Vujčić, V., “Semidefinite programming methods for the symmetric travelling salesman problem”, in: G. Cornuejols, R.E. Burkard, G.J. Woeginger (eds.), Integer Programming and Combinatorial Optimization, Proc. 7th Int. IPCO Conf., Graz, Austria, June 1999, Lecture Notes Comp. Sci. 1610, Springer, Berlin, 1999, 126-136.

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

Cvetković, D., Simić, S., Caporossi, G., and Hansen, P., “Variable Neighborhood Search for extremal graphs, 3. On the largest eigenvalue of color-constrained trees“, Linear and Multilinear Algebra, 49 (2001) 143-160.

Fowler, P.W., Hansen, P., Caporossi, G., and Sondini, A., “Variable Neighborhood Search for extremal graphs, 7. Polyenes with maximum HOMO-LUMO gap”, Chem. Phys. Letters, 49 (2001) 143-146.

Gerber, M.U., Hansen, P., and Hertz, A., “Extensions of Turán's theorem to the 2-stability number”, Graphs Combin., 18 (3) (2002) 479-489.

Gutman, I., Hansen, P., and Mélot, H., “Variable Neighborhood Search for extremal graphs, 10. Comparison of irregularity indices for chemical trees”, to appear.

Hansen, P., and Mélot, H., “Variable Neighborhood Search for extremal graphs, 6. Analyzing bounds for the connectivity index”, J. Chem. Inform. Comput. Sci., 43 (2003) 1-14.

Hansen, P., and Mélot, H., “Variable Neighborhood Search for extremal graphs, 9. Bounding irregularity of a graph”, to appear.

Hansen, P., and Mladenović, N., “Variable Neighborhood Search: Principles and applications”, EJOR, 130 (2001) 449-467.

Lovász, L., and Pelikan, S., “On the eigenvalues of trees”, Periodica Math. Hung., 3 (1-2) (1973) 175-182.

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

McKay, B.D., “Isomorph-free exhaustive generation”, J. Algorithms, 26 (1998) 306-324.

Mladenović, N., and Hansen, P., “Variable Neighborhood Search”, Comp. Oper. Res., 24 (1997) 1097-1100.

Petrović, R., Guberinić, S., Batanović, V., and Cvetković, D., “Operational research models in action, the result of international cooperation, a potpourri”, EJOR, 87 (1995) 500-506.

Turán, P., “Eine extremalaufgabe aus der graphentheorie”, Fiz. Mat. Lapok, 48 (1941) 436-452.

Downloads

Published

2004-09-01

Issue

Vol. 14 No. 2 (2004)

Section

Research Articles

License

Copyright (c) 2004 YUJOR

Creative Commons License

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