1992-93 Special Year on Combinatorial Optimization

One way in which DIMACS evaluates the success of its special years is by compiling a list of publications that could be traced to the year in some way, which means that the work was partly done during a special year event, or the collaboration was started during a special year event, and the like.

Reference List:

  1. Applegate, D., Bixby, R., Chvatal, V. and Cook, W., On the solution of traveling salesman problems, Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians, (1998), 645 - 656.

  2. Barany, L and Onn, S., Caratheodory's theorem: colourful and applicable, Bolyai Society Mathematical Studies, (I. Barany and K. Boroczky eds.), 6 (1997), 11-21, North-Holland.

  3. Barany, L and Onn, S., Colourful linear programming, Integer Programming and Combinatorial Optimization, 5th IPCO Proc., (W.H. Cunningham, S.T. McCormick and M. Queyranne eds.), Lecture Notes in Computer Science, 1084 (1996), 1-15, Springer-Verlag.

  4. Barany, L. and Onn, S., Colourful linear programming and its relatives, Mathematics of Operations Research, 22 (1997), 550-567.

  5. Brown, J.I. and Colbourn, C.J., On the log concavity of reliability and matroidal sequences, Adv. Appl. Math., 15 (1994), 114-127.

  6. Colbourn, C.J., Some open problems for reliability polynomials, Proc. Twentyfourth Southeastern Conf. Combin., Graph Theory Computing, Congr. Numer. 93 (1993), 187-202.

  7. Colbourn, C.J., Provan, J.S. and Vertigan, D., The complexity of computing the Tutte polynomial on transversal matroids, Combinatorica, 15 (1995), 1-10.

  8. Colbourn, C.J., Nel, L.D., Boffey, T.B. and Yates, D.F., Network reliability and the probabilistic estimation of damage from fire spread, Ann. Oper. Res., 50 (1994), 173-185.

  9. Colbourn, C.J., Mendelsohn, E., Rosa, A. and Siran J., The spectrum of anti-mitre Steiner triple systems, Graphs Combinat., 10 (1994), 215-224.

  10. Deza, M. and Onn, S., Lattice-free polytopes and their diameter, Discrete and Computational Geometry, 13 (1995), 59 -75.

  11. Erickson, D.L. and Colbourn, C.J., Combinatorics and the conflict-free access problem, Proc. Twentyfourth Southeastern Conf. Combin., Graph Theory Computing, Congr. Numer., 94 (1993), 115-121.

  12. Farach, M. and Thorup, M., Fast comparison of evolutionary trees, Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), (1994), 481-488.

  13. Farach, M. and Thorup, M., Fast Comparison of Evolutionary Trees, Information and Computation, 123 (1995), 29-37.

  14. Farach, M. and Thorup, M., Optimal evolutionary tree comparison by sparse dynamic programming, Proceedings of the 35th IEEE Symposium on Foundations of Computer Science (FOCS), (1994), 770-779.

  15. Farach, M. and Thorup, M., Sparse Dynamic Programming for Evolutionary-Tree Comparison, SIAM Journal on Computing, 26 (1997), 210-230.

  16. Frank, A., Karzanov, A. and Sebo, A., On multiflow maximization, SIAM Journal of Discrete Mathematics, (1997), 158-170.

  17. Galluccio, A., Gargano, L., Korner, J. and Simonyi, G., Different capacities of a digraph, Graphs and Combinatorics, 10 (1994), 105-121.

  18. Galluccio, A., Simonovits, M. and Simonyi, G., On the structure of co-critical graphs, Graph Theory, Combinatorics, and Applications, Proc. Seventh International Conference on Graph Theory, Combinatorics, Algorithms and Applications, (Y Alavi and A. Schwenk eds.), John Wiley and Sons, (1995), 1053-1071.

  19. Goemans, M.X., Goldberg, A.V., Plotkin, S., Shmoys, D.B., Tardos, E. and Williamson, D.P., Improved approximation algorithms for network design problems, Proceedings of the Fifth Annual Symposium on Discrete Algorithms, (1994), 223-232.

  20. Harms, D.D. and Colbourn, C.J., Evaluating performability: most probable states and bounds, Telecomm. Syst., 2 (1994), 275-300.

  21. Helmberg, C., Poljak, S., Rendl, F. and Wolkowicz, H., Combining semidefinite and polyhedral relaxations for integer programs, Integer Programming and Combinatorial Optimization (Copenhagen, 1995), 124-134, Springer, Berlin.

  22. Helmberg, C., Poljak, S., Rendl, F. and Wolkowicz, H., An interior-point method for semidefinite programming, SIAM J. Optim., 6 (1996), 342-361.

  23. Jagota, A., Sanchis, L. and Ganesan, R., Approximately solving maximum clique using neural network and related heuristics, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge (David S. Johnson and Michael A. Trick, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, (1996).

  24. Kraetzl, M, Colbourn, C.J. and Devitt, J.S., Bounding Techniques for the Reliability of Multistage Interconnection Networks, Proceedings of IEEE Singapore International Conference on Networks/International Conference on Information Engineering '93, (1993), 766-770.

  25. Kratochvil, J. and Sebo, A., Coloring Precolored Perfect Graphs, Journal of Graph Theory, 25 (1997), 207-216.

  26. Onn, S., A colorful determinantal identity, a conjecture of Rota, and Latin squares, The American Mathematical Monthly, 104 (1997), 156-159.

  27. Onn, S., Hilbert series of group representations and Grobner bases for generic modules, Journal of Algebraic Combinatorics, 3 (1994), 187-206.

  28. Pardalos, P. and Wolkowicz, H., eds., Quadratic Assignment and Related Problems, American Mathematical Society, Providence, RI, 1994. Papers from the workshop held at Rutgers University, New Brunswick, New Jersey, May 20-21, 1993.

  29. Pardalos, P. and Wolkowicz, H., eds., The quadratic assignment problem: a survey and recent developments, Quadratic assignment and related problems (New Brunswick, NJ, 1993), 1-42. Amer. Math. Soc., Providence, RI, 1994.

  30. Poljak, S., Rendl, F. and Wolkowicz, H., A recipe for semidefinite relaxation for $(0,1)$-quadratic programming, J. Global Optim., 7 (1995), 51-73.

  31. Poljak, S. and Wolkowicz, H., Convex relaxations of $(0,1)$-quadratic programming, Math. Oper. Res., 20 (1995), 550-561.

  32. Raz, R., Fourier analysis for probabilistic communication complexity, Computational Complexity, 5 (1995), 205-221.

  33. Raz, R. and Spieker, B., On the 'Log-Rank' conjecture in communication complexity, Proceeding of the 34th FOCS, (1993), 168-177. Journal version in Combinatorica, 15 (1995), 567-588.

  34. Rendl, R., Vanderbei, R.J. and Wolkowicz, H., Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems, Optim. Methods Softw., 5 (1995), 1-16.

  35. Sanchis, L. and Jagota, A., Some experimental and theoretical results on test case generators for the maximum clique problem, INFORMS Journal on Computing, 8 (1996), 87-102.

  36. Sebo, A., Forcing Colorations and the Perfect graph conjecture, Integer Programming and Combinatorial Optimization 2 (Balas, Cornuejols and Kannan eds.), Carnegie Mellon University Press (1992).

  37. Sebo, A., Plane multiflows with a fixed number of demands, Journal of Combinatorial Theory, 59 (1993), 163-171.

  38. Sebo, A., On critical edges in minimal imperfect graphs, Journal of Combinatorial Theory, 67 (1996), 62-85.

  39. Sebo, A., On the connectivity of minimal imperfect graphs, Journal of Graph Theory, 23 (1996), 77-85.

  40. Simonyi, G., Entropy splitting hypergraphs, J. Combin. Theory Ser. B, 66 (1996), 310-323.

  41. Simonyi, G., Graph entropy: a survey, Combinatorial Optimization, (W. Cook, L. Lovasz, and P. Seymour, eds.) DIMACS Series in Discrete Mathematics and Computer Science, 20 (1995), 399-441.

  42. Syrotiuk, V.R., Colbourn, C.J., Klarner, D.A. and Pachl, J., Characterizing Wang tilings using finite automata, Proc. Third International Workshop on Polyominoes and Tilings, Toulouse, France, (1994), 11-30.

  43. Thorup, M., Parallel Shortcutting of Rooted Trees, Journal of Algorithms, 23 (1997), 139-159.

  44. Vanderbei, R.J. and Benson, H.Y., On Formulating Semidefinite Programming Problems as Smooth Convex Nonlinear Optimization Problems, TechReport VY99, Department of Operations Research and Financial Engineering, Princeton University, ORFE 99-01, (1999).

  45. Wolkowicz, H. and Zhao, Q., Semidefinite relaxations for the graph partitioning problem, Discrete Applied Math., 96-97 (1999), 461-479.

  46. Zhao, Q., Karisch, S.E., Rendl, R. and Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem, J. Comb. Optim., 2 (1998), 71-109.

Up. Index of DIMACS Special Years
DIMACS Homepage
Contacting the Center
Document last modified on June 12, 2000.