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:
- 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.
- 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.
- 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.
- Barany, L. and Onn, S.,
Colourful linear programming and its relatives,
Mathematics of Operations Research, 22 (1997), 550-567.
- Brown, J.I. and Colbourn, C.J.,
On the log concavity of reliability and matroidal sequences,
Adv. Appl. Math., 15 (1994), 114-127.
- Colbourn, C.J.,
Some open problems for reliability polynomials,
Proc. Twentyfourth Southeastern Conf. Combin., Graph Theory Computing,
Congr. Numer. 93 (1993), 187-202.
- Colbourn, C.J., Provan, J.S. and Vertigan, D.,
The complexity of computing the Tutte polynomial on transversal matroids,
Combinatorica, 15 (1995), 1-10.
- 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.
- Colbourn, C.J., Mendelsohn, E., Rosa, A. and Siran J.,
The spectrum of anti-mitre Steiner triple systems,
Graphs Combinat., 10 (1994), 215-224.
- Deza, M. and Onn, S.,
Lattice-free polytopes and their diameter,
Discrete and Computational Geometry, 13 (1995), 59 -75.
- 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.
- Farach, M. and Thorup, M.,
Fast comparison of evolutionary trees,
Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA),
(1994), 481-488.
- Farach, M. and Thorup, M.,
Fast Comparison of Evolutionary Trees,
Information and Computation, 123 (1995), 29-37.
- 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.
- Farach, M. and Thorup, M.,
Sparse Dynamic Programming for Evolutionary-Tree Comparison,
SIAM Journal on Computing, 26 (1997), 210-230.
- Frank, A., Karzanov, A. and Sebo, A.,
On multiflow maximization,
SIAM Journal of Discrete Mathematics, (1997), 158-170.
- Galluccio, A., Gargano, L., Korner, J. and Simonyi, G.,
Different capacities of a digraph,
Graphs and Combinatorics, 10 (1994), 105-121.
- 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.
- 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.
- Harms, D.D. and Colbourn, C.J.,
Evaluating performability: most probable states and bounds,
Telecomm. Syst., 2 (1994), 275-300.
- 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.
- Helmberg, C., Poljak, S., Rendl, F. and Wolkowicz, H.,
An interior-point method for semidefinite programming,
SIAM J. Optim., 6 (1996), 342-361.
- 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).
- 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.
- Kratochvil, J. and Sebo, A.,
Coloring Precolored Perfect Graphs,
Journal of Graph Theory, 25 (1997), 207-216.
- Onn, S.,
A colorful determinantal identity, a conjecture of Rota, and Latin squares,
The American Mathematical Monthly, 104 (1997), 156-159.
- Onn, S.,
Hilbert series of group representations and Grobner bases for generic modules,
Journal of Algebraic Combinatorics, 3 (1994), 187-206.
- 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.
- 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.
- Poljak, S., Rendl, F. and Wolkowicz, H.,
A recipe for semidefinite relaxation for $(0,1)$-quadratic programming,
J. Global Optim., 7 (1995), 51-73.
- Poljak, S. and Wolkowicz, H.,
Convex relaxations of $(0,1)$-quadratic programming,
Math. Oper. Res., 20 (1995), 550-561.
- Raz, R.,
Fourier analysis for probabilistic communication complexity,
Computational Complexity, 5 (1995), 205-221.
- 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.
- 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.
- 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.
- 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).
- Sebo, A.,
Plane multiflows with a fixed number of demands,
Journal of Combinatorial Theory, 59 (1993), 163-171.
- Sebo, A.,
On critical edges in minimal imperfect graphs,
Journal of Combinatorial Theory, 67 (1996), 62-85.
- Sebo, A.,
On the connectivity of minimal imperfect graphs,
Journal of Graph Theory, 23 (1996), 77-85.
- Simonyi, G.,
Entropy splitting hypergraphs,
J. Combin. Theory Ser. B, 66 (1996), 310-323.
- 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.
- 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.
- Thorup, M.,
Parallel Shortcutting of Rooted Trees,
Journal of Algorithms, 23 (1997), 139-159.
- 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).
- Wolkowicz, H. and Zhao, Q.,
Semidefinite relaxations for the graph partitioning problem,
Discrete Applied Math., 96-97 (1999), 461-479.
- 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.
Index of DIMACS Special Years
DIMACS Homepage
Contacting the Center
Document last modified on June 12, 2000.