En mi opinión, unos como estos:
Edmonds, Jack: flores, árboles y flores (1965)
(algoritmo de coincidencia máxima)
Hopcroft, John y Robert E. Tarjan: Pruebas de planaridad eficientes (1974)
(prueba de planaridad de tiempo lineal y ubicación del subgrafo de kuratowski)
- ¿Quiénes son las estrellas en ascenso en la informática teórica?
- ¿Cuál es el algoritmo más eficiente para encontrar todos los picos 2D en una matriz?
- ¿Cuáles son algunos artículos clásicos sobre teoría de grafos?
- ¿Qué es una máquina de Turing no determinista?
- ¿Cuál es la longitud esperada de la subsecuencia creciente más larga?
Appel, Kenneth y Wolfgang Haken: “Solución del problema del mapa de cuatro colores” (octubre de 1977)
(primer ejemplo de una prueba computarizada)
Graham, Ronald L. y Bruce L. Rothschild: “El teorema de Ramsey para conjuntos de parámetros n” (1971)
(solución a uno de los problemas más famosos de la teoría de Ramsey que involucra uno de los números más grandes jamás vistos en una prueba)
Rado, Richard: “Gráficos universales y funciones universales” (1964)
(Una descripción moderna del gráfico infinito, aunque Ackermann lo describió un poco antes)
Dijkstra, Edsger W .: “Una nota sobre dos problemas en relación con los gráficos” (1959)
(Algoritmo de Dijkstra)
Ford, Lester R. y Delbert R. Fulkerson: “Flujo máximo a través de una red” (1956)
(Algoritmo Ford-Fulkerson)
Aldous, David J .: La construcción de caminata aleatoria de árboles que se extienden de manera uniforme y árboles con etiqueta uniforme. (1990)
(un algoritmo muy simple para un árbol de expansión uniforme; vea también el algoritmo de Wilson para un algoritmo más rápido creado 6 años después)
(También hay algunos buenos documentos de algoritmos de aproximación, pero no puedo elegir el ejemplo “más clásico”, así que lo dejaré a otros).
