References

1

Alon, N., A parallel algorithmic version of the local lemma, Random Structures and Algorithms (1991), 367-378.

2

Alon, N., Duke, R.A., Lefmann, H., Rödl, V., Yuster, R., The algorithmic aspects of the regularity lemma, J. of Algorithms (1994), 80-109.

3

Alon, N., Spencer, J.H., The Probabilistic Method, John Wiley and Sons, Inc., New York 1992, pp.

4

Althöfer, I., Das, G., Dobkin, D., Joseph, D., Soares. J., On sparse spanners of weighted graphs, Discrete Comp. Geom., 9:81-100, 1993.

5

Applegate, D., Bixby, R., Cook, W., Chavátal, V., em preparação (1993).

6

Arkin, E.M., Papadimitriou, C.H., Yannakakis, M., Modularity of cycles and paths in graphs, J. ACM (2) (1991), 225-274.

7

Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M., Proof verification and hardness of approximation problems, in 33rd Foundations of Computer Science (1992).

8

Barahona, F., Mahjoub, A.R., On the cut polytope, Mathematical Programming (1986), 157-173.

9

Beck, J., An algorithmic approach to the Lov�sz local lemma I, Random Structures and Algorithms (1991), 343-365.

10

Benatti, H., Hashimoto, R., Wakabayashi, Y., Modularidade de circuitos e caminhos em grafos, em preparação (1994).

11

Bollobás, B., Kohayakawa, Y., uczak, T., The evolution of random subgraphs of the cube, Random Structures and Algorithms (1992), 55-90.

12

Bollobás, B., Kohayakawa, Y., uczak, T., On the evolution of random Boolean functions, Extremal Problems for Finite Sets (Frankl, P., Füredi, Z., Katona, G.O.H., Miklós, D., eds), a aparecer, 1993.

13

Bollobás, B., Kohayakawa, Y., uczak, T., On the diameter and radius of random subgraphs of the cube, Random Structures and Algorithms, a aparecer.

14

Bollobás, B., Kohayakawa, Y., uczak, T., Connectivity properties of random subgraphs of the cube, submetido.

15

Brightwell, G.R., Kohayakawa, Y., Ramsey properties of orientations of graphs, Random Structures and Algorithms (1993), 413-428.

16

Chandra, B., Das, G., Narasimhan, G., Soares. J., New sparseness results on graph spanners, in Proc. 8th ACM Symp. Computational Geometry (1992), pp 192-201,

17

Dahab, R., The Birkhoff-Lewis Equations, PhD thesis, University of Waterloo, 1993.

18

Dyer, M.E., e Frieze, A.M., Computing the volume of convex bodies: a case where randomness provably helps, in Probabilistic Combinatorics and its Applications (Bollobás, B., ed.), Proceedings of Symposia in Applied Mathematics 44, American Mathematical Society, Providence 1991, pp. 123-169

19

Feofiloff, P., Lucchesi, C.L. Algoritmos para igualdades minimax em grafos. VI Escola de Computa�ão, Campinas, SP, 1988.

20

Feofiloff, P., Younger, D.H. Directed cut transversal packing for source-sink connected graphs. Combinatorica (1987), 255-263.

21

Ferreira, C.E., Grötschel, M., Kiefl, S., Krispenz, C., Martin, A., Weismantel, R., Some integer programs arising in the design of main-frame computers, ZOR (1993), 77-100.

22

Ferreira, C.E., Grötschel, M., Martin, A., Weismantel, R., Facets for the multiple knapsack polytope Konrad-Zuse-Zentrum f�r Informationstechnik Berlin, Relat�rio SC93-04, submetido (1993).

23

Ferreira, C.E., Grötschel, M., Martin, A., Weismantel, R., A cutting plane based algorithm for the multiple knapsack problem, Konrad-Zuse-Zentrum f�r Informationstechnik Berlin, Relat�rio SC93-07, submetido (1993).

24

de Figueiredo, C., Um Estudo de Problemas Combinatórios em Grafos Perfeitos, Tese de Doutorado, COPPE/UFRJ, Rio de Janeiro, 1991.

25

de Figueiredo, C., Tardif, V., Some Problems on Perfect Graphs, Research Report CORR 89-31, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, 1989.

26

Graham, R.L., Rödl, V., Numbers in Ramsey theory, em Surveys in Combinatorics (Whitehead, C., ed.), LMS Lecture Note Series 123, CUP, Cambridge 1987, pp. 111-153.

27

Grötschel, M., Jünger, M., Reinelt, G., A cutting plane algorithm for the linear ordering problem, Oper. Research (1985), 1195-1220.

28

Grötschel, M., Wakabayashi, Y., On the Structure of the Monotone Asymmetric Travelling Salesman Polytope I: Hypohamiltonian Facets, Discrete Mathematics (1981), 43-59.

29

Grötschel, M., Wakabayashi, Y., On the Structure of the Monotone Asymmetric Travelling Salesman Polytope II: Hypotraceable Facets, Mathematical Programming Study (1981), 77-97.

30

Grötschel, M., Wakabayashi, Y., A cutting plane algorithm for a clustering problem, Mathematical Programming B (1989), 59-96.

31

Grötschel, M., Wakabayashi, Y., Facets of the clique partitioning problem, Mathematical Programming A (1990), 367-387.

32

Gurgel, M.A.C.M, Poliedros de Grafos Transitivos, Tese de doutorado, Instituto de Matem�tica e Estat�tica da USP, 1992.

33

Gurgel, M.A.C.M., Wakabayashi, Y., The Diameter of the Complete Pre-order Polytope, Relatório Técnico RT-MAC 9309, submetido para publicação.

34

Gurgel, M.A.C.M., Wakabayashi, Y., The Complete Pre-order Polytope: Facets and Separation Problem, Relatório Técnico RT-MAC 9306, submetido para publicação.

35

Haxell, P.E., Kohayakawa, Y., On an anti-Ramsey property of Ramanujan graphs, submetido.

36

Haxell, P.E., Kohayakawa, Y., The size-Ramsey number of trees, Israel J. of Math., a aparecer.

37

Haxell, P.E., Kohayakawa, Y., uczak, T., The induced size-Ramsey number of cycles, submetido.

38

Haxell, P.E., Kohayakawa, Y., uczak, T., Tur�n's extremal problem in random graphs: forbidding odd cycles, submetido.

39

Haxell, P.E., Kohayakawa, Y., uczak, T., Tur�n's extremal problem in random graphs: forbidding even cycles, em prepara��o.

40

Janson, S., uczak, T., Knuth, D.E., Pittel, B., The birth of the giant component, Random Structures and Algorithms (1993), 233-358.

41

Jones, V.F.R., A polynomial invariant for links via von Neumann algebras. Bull. Amer. Math. Soc., 129:103-112, 1986.

42

Kauffman, L.H., State Models and the Jones Polynomial. Topology, 26:395-407, 1987.

43

Kauffman, L.H., Knots and Physics. World Scientific Pub, 1991.

44

Kohayakawa, Y., A note on induced cycles in Kneser graphs, Combinatorica, 11:245-251, 1991.

45

Kohayakawa, Y., The regularity lemma of Szemerédi for sparse graphs, manuscrito, 1993.

46

Kohayakawa, Y., uczak, T., Sparse anti-Ramsey graphs, submetido.

47

Kohayakawa, Y., uczak, T., Rödl, V., Ramsey-type results for oriented trees, submetido.

48

Korte, N., Möhring, R.H., An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18(1):68-81, 1989.

49

Lauer, E., Szwarcfiter, J.L., A search strategy for the elementary cycles of a direct graph, BIT (1976), 192-204.

50

Li, K., Cheng, K.-H., Complexity of resource allocation and job scheduling problems in partitionable mesh connected systems, in Proc. First Annual IEEE Symposium of Parallel and Distributed Processing, Silver Spring, MD (1989), pp. 358-365.

51

Li, K., Cheng, K.-H., On three-dimensional packing, SIAM J. Comput. (1990), 847-867.

52

Lovász, L. and Simonovits, M., Random walks in a convex body and an improved volume algorithm, Random Structures and Algortihms (1993), 359-412.

53

Lubiw, A., A note on odd/even cycles, Discrete Applied Math. 22 (1988/89) 87-92.

54

Lucchesi, C.L., de Mello, C.P., Szwarcfiter, J.L., On clique-complete graphs, submetido.

55

Lucchesi, C.L., Younger, D.H. A minimax theorem for directed graphs. J. of the London Math. Soc. (1978), 369-374.

56

Lucchesi, C.L., Younger, D.H. An -transversal theorem for bipartite graphs, manuscrito, 1991.

57

Martin, A., Packungen von Steinerbäume, PhD Dissertation, Technische Universität Berlin, 1992.

58

Meidanis, J., Algorithms for Problems in Computational Genetics, PhD thesis, University of Wisconsin-Madison, 1992.

59

de Mello, C.P., Sobre grafos clique-completos, Tese de Doutoramento, COPPE/UFRJ, Rio de Janeiro, 1992.

60

Micali, S., Vazirani, V.V., An algorithm for finding maximum matching in general graphs, em Proceedings of the IEEE Twenty-First Annual Symposium on Foundations of Computer Science (1980), pp. 17-27.

61

Padberg, M.W., Grötschel, M., Polyhedral aspects of the travelling salesman problen III: computation'', in The Travelling Salesman Problem (Lawler, E.L. et al. eds), Wiley and Sons, London/New York 1985.

62

Padberg, M.W., Rinaldi, G., A branch-and-cut algorithm for the solution of large-scale traveling salesman problems, SIAM Review (1991), 1-41.

63

Porto, O., Ciclos Induzidos Pares em Grafos Planares, Tese de Doutorado, COPPE/UFRJ, Rio de Janeiro, (1992).

64

Ramalingan, G., Pandu Rangan, C., A unified approach to domination problems on interval graphs. Inform. Process. Lett., 27:271-274, 1988.

65

Rödl, V., Rucinski, A., Lower bounds on probability thresholds for Ramsey properties, Combinatorics, Paul Erdos is Eighty (Volume 1), Keszthely (Hungary), Bolyai Soc. Math. Studies, 1993, pp. 317-346.

66

Rödl, V., Rucinski, A., Threshold functions for Ramsey properties, Journal of the Amer. Math. Soc., a aparecer.

67

Saleur, H., Zeroes of Chromatic Polynomials: A New Approach to Beraha Conjecture Using Quantum Groups. Commun. Math. Phys., 132:657-679, 1990.

68

Scheithauer, G., A three-dimensional bin-packing algorithm, J. Information Processing and Cybernetics 5/6 (formerly EIK: Elektronische Informationsverarbeitung und Kybernetik) (1991), 263-271.

69

Schrijver, A. Min max relations for directed graphs. Annals of Discrete Math. (1982), 261-280.

70

Setubal, J., New experimental results for bipartite matchings, em Proc. Netflow93, San Miniato, 1993.

71

Seymour. P.D., Thomassen, C., Characterization of even directed graphs, J. Comb. Th. B (1987), 36-45.

72

Simon, K., A new simple linear algorithm to recognize interval graphs, em Proc. of the Inter. Workshop on Computational Geometry CG'91, Lecture Notes in Comp. Sci. (1991), pp. 289-308.

73

Soares, J., Maximum diameter of regular digraphs, Journal of Graph Theory (1992), 437-450.

74

Soares, J., Graph spanners: a survey, in Congressus Numerantium (1992), pp. 225-238.

75

de Souza, P.S., Asynchronous Organizations for Multi-Algorithm Problems, PhD thesis, Carnegie Mellon University, 1993.

76

Tutte, W.T., The matrix of chromatic joins. J. Combinatorial Theory (B), 57(2):269-288, 1993.

77

Woodall, D.R. Menger and K�nig systems. Lecture Notes in Mathematics 642, Springer-Verlag 1978.