Hispanopedia Wiki
Articulo de referencia

camino euleriano

Los multigrafos de los rompecabezas de los puentes de Königsberg y de las cinco habitaciones tienen más de dos vértices impares (en naranja), por lo que no son eulerianos y, por...

Hispanopedia WikiContenido en espanolLectura gratuita
Los multigrafos de los rompecabezas de los puentes de Königsberg y de las cinco habitaciones tienen más de dos vértices impares (en naranja), por lo que no son eulerianos y, por lo tanto, los rompecabezas no tienen solución.
Cada vértice de este grafo tiene un grado par. Por lo tanto, se trata de un grafo euleriano. Siguiendo las aristas en orden alfabético se obtiene un circuito/ciclo euleriano.

En teoría de grafos , un camino euleriano (o sendero euleriano ) es un recorrido en un grafo finito que visita cada arista exactamente una vez (permitiendo volver a visitar los vértices). De manera similar, un circuito euleriano o ciclo euleriano es un recorrido euleriano que comienza y termina en el mismo vértice . Fueron descritos por primera vez por Leonhard Euler al resolver el famoso problema de los siete puentes de Königsberg en 1736. El problema se puede plantear matemáticamente de la siguiente manera:

Dado el gráfico de la imagen, ¿es posible construir un camino (o un ciclo ; es decir, un camino que comienza y termina en el mismo vértice) que visite cada arista exactamente una vez?

Euler demostró que una condición necesaria para la existencia de circuitos eulerianos es que todos los vértices del grafo tengan grado par , y afirmó, sin demostración, que los grafos conexos con todos los vértices de grado par tienen un circuito euleriano. La primera demostración completa de esta última afirmación fue publicada póstumamente en 1873 por Carl Hierholzer . [ 1 ] Esto se conoce como el Teorema de Euler.

Un grafo conexo tiene un ciclo de Euler si y solo si cada vértice tiene un número par de aristas incidentes.

El término grafo euleriano tiene dos significados comunes en la teoría de grafos. Un significado es un grafo con un circuito euleriano, y el otro es un grafo con todos los vértices de grado par. Estas definiciones coinciden para grafos conexos. [ 2 ]

Para que existan caminos eulerianos, es necesario que cero o dos vértices tengan grado impar ; esto significa que el grafo de Königsberg no es euleriano. Si no hay vértices de grado impar, todos los caminos eulerianos son circuitos. Si hay exactamente dos vértices de grado impar, todos los caminos eulerianos comienzan en uno de ellos y terminan en el otro. Un grafo que tiene un camino euleriano pero no un circuito euleriano se denomina semi-euleriano .

Definición

Un camino euleriano , [ nota 1 ] o paseo euleriano , en un grafo no dirigido es un camino que utiliza cada arista exactamente una vez. Si existe tal camino, el grafo se denomina transitable o semi-euleriano . [ 3 ]

Un ciclo euleriano , [ nota 1 ] también llamado circuito euleriano o recorrido euleriano , en un grafo no dirigido es un circuito que utiliza cada arista exactamente una vez. Si existe tal ciclo, el grafo se llama euleriano o unicursal . [ 4 ] El término "grafo euleriano" también se usa a veces en un sentido más débil para denotar un grafo donde cada vértice tiene grado par. Para grafos conexos finitos , las dos definiciones son equivalentes, mientras que un grafo posiblemente no conexo es euleriano en el sentido más débil si y solo si cada componente conexa tiene un ciclo euleriano.

Para grafos dirigidos , "path" debe reemplazarse por directed path y "cycle" por directed cycle .

La definición y las propiedades de los caminos, ciclos y grafos eulerianos también son válidas para los multigrafos .

Una orientación euleriana de un grafo no dirigido G es una asignación de una dirección a cada arista de G tal que, en cada vértice v , el grado de entrada de v es igual al grado de salida de v . Dicha orientación existe para cualquier grafo no dirigido en el que cada vértice tiene grado par, y puede encontrarse construyendo un recorrido euleriano en cada componente conexa de G y luego orientando las aristas según el recorrido. [ 5 ] Toda orientación euleriana de un grafo conexo es una orientación fuerte , una orientación que hace que el grafo dirigido resultante sea fuertemente conexo .

Propiedades

  • Un grafo no dirigido tiene un ciclo euleriano si y solo si cada vértice tiene grado par, y todos sus vértices con grado distinto de cero pertenecen a una única componente conexa . [ 6 ]
  • Un grafo no dirigido puede descomponerse en ciclos disjuntos por aristas si y solo si todos sus vértices tienen grado par. Por lo tanto, un grafo tiene un ciclo euleriano si y solo si puede descomponerse en ciclos disjuntos por aristas y sus vértices de grado distinto de cero pertenecen a una única componente conexa.
  • Un grafo no dirigido tiene un camino euleriano si y solo si exactamente cero o dos vértices tienen grado impar, y todos sus vértices con grado distinto de cero pertenecen a una única componente conexa. [ 6 ]
  • Un grafo dirigido tiene un ciclo euleriano si y solo si cada vértice tiene el mismo grado de entrada y de salida , y todos sus vértices con grado distinto de cero pertenecen a una única componente fuertemente conexa . De forma equivalente, un grafo dirigido tiene un ciclo euleriano si y solo si puede descomponerse en ciclos dirigidos disjuntos en aristas y todos sus vértices con grado distinto de cero pertenecen a una única componente fuertemente conexa. [ 6 ]
  • Un grafo dirigido tiene un camino euleriano si y solo si como máximo un vértice tiene ( grado de salida ) − ( grado de entrada ) = 1, como máximo un vértice tiene (grado de entrada) − (grado de salida) = 1, todos los demás vértices tienen igual grado de entrada y grado de salida, y todos sus vértices con grado distinto de cero pertenecen a una única componente conexa del grafo no dirigido subyacente. [ 6 ]

Construcción de senderos y circuitos eulerianos

Utilizar el método de Euler para resolver acertijos que implican dibujar una forma con un trazo continuo:
  1. Como el rompecabezas de Haus vom Nikolaus tiene dos vértices de grado impar (naranja), el camino debe comenzar en uno y terminar en el otro.
  2. Una variante con cuatro vértices de grado impar no tiene solución.
  3. Si no hay vértices de grado impar, el sendero puede comenzar en cualquier punto y forma un ciclo euleriano.
  4. Los extremos sueltos se consideran vértices de grado 1.
  5. El gráfico también debe estar conectado.

El algoritmo de Fleury

El algoritmo de Fleury es un algoritmo elegante pero ineficiente que data de 1883. [ 7 ] Consideremos un grafo que se sabe que tiene todas las aristas en el mismo componente y como máximo dos vértices de grado impar. El algoritmo comienza en un vértice de grado impar o, si el grafo no tiene ninguno, comienza con un vértice elegido arbitrariamente. En cada paso elige la siguiente arista en el camino que sea una cuya eliminación no desconectaría el grafo, a menos que no exista tal arista, en cuyo caso elige la arista restante que queda en el vértice actual. Luego se mueve al otro extremo de esa arista y la elimina. Al final del algoritmo no quedan aristas, y la secuencia de la que se eligieron las aristas forma un ciclo euleriano si el grafo no tiene vértices de grado impar, o un camino euleriano si hay exactamente dos vértices de grado impar.

Mientras que el recorrido del grafo en el algoritmo de Fleury es lineal en el número de aristas, es decirO(|mi|){\displaystyle O(|E|)}, también debemos tener en cuenta la complejidad de detectar puentes . Si volvemos a ejecutar el algoritmo de búsqueda de puentes de tiempo lineal de Tarjan [ 8 ] después de la eliminación de cada arista, el algoritmo de Fleury tendrá una complejidad temporal deO(|mi|2){\displaystyle O(|E|^{2})}. Un algoritmo dinámico de búsqueda de puentes de Thorup (2000) permite mejorar esto aO(|mi|⋅registro3⁡|mi|⋅registro⁡registro⁡|mi|){\displaystyle O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)}, pero esto sigue siendo significativamente más lento que los algoritmos alternativos.

El algoritmo de Hierholzer

El artículo de Hierholzer de 1873 proporciona un método diferente para encontrar ciclos de Euler que es más eficiente que el algoritmo de Fleury:

  • Elija cualquier vértice inicial v y siga una secuencia de aristas desde ese vértice hasta regresar a v . No es posible quedarse atascado en ningún otro vértice que no sea v , ya que el grado par de todos los vértices garantiza que, cuando la secuencia entra en otro vértice w, debe haber una arista sin usar que salga de w . El recorrido formado de esta manera es un recorrido cerrado, pero puede que no cubra todos los vértices y aristas del grafo inicial.
  • Siempre que exista un vértice u que pertenezca al recorrido actual pero que tenga aristas adyacentes que no formen parte del recorrido, inicie otro recorrido desde u , siguiendo las aristas no utilizadas hasta regresar a u , y una el recorrido formado de esta manera al recorrido anterior.
  • Dado que asumimos que el grafo original es conexo , repetir el paso anterior agotará todas las aristas del grafo.

Al utilizar una estructura de datos como una lista doblemente enlazada para mantener el conjunto de aristas no utilizadas incidentes a cada vértice, para mantener la lista de vértices en el recorrido actual que tienen aristas no utilizadas y para mantener el recorrido en sí, las operaciones individuales del algoritmo (encontrar aristas no utilizadas que salen de cada vértice, encontrar un nuevo vértice de inicio para un recorrido y conectar dos recorridos que comparten un vértice) se pueden realizar en tiempo constante cada una, por lo que el algoritmo general toma un tiempo lineal .O(|mi|){\displaystyle O(|E|)}. [ 9 ]

Este algoritmo también puede implementarse con una cola doble . Dado que solo es posible quedarse atascado cuando la cola doble representa un recorrido cerrado, se debe rotar la cola doble eliminando aristas de la cola y añadiéndolas a la cabeza hasta que se desbloquee, y luego continuar hasta que se hayan considerado todas las aristas. Esto también toma un tiempo lineal, ya que el número de rotaciones realizadas nunca es mayor que|mi|{\displaystyle |E|}(Intuitivamente, cualquier borde "malo" se mueve a la cabeza, mientras que los bordes nuevos se agregan a la cola).

Conteo de circuitos eulerianos

Problemas de complejidad

El número de circuitos eulerianos en un grafo dirigido se puede calcular mediante el teorema BEST , que recibe su nombre de de Bruijn , van Aardenne- Ehrenfest , Smith y Tutte . La fórmula establece que el número de circuitos eulerianos en un digrafo es el producto de ciertos factoriales de grado y el número de arborescencias con raíz . Este último se puede calcular como un determinante mediante el teorema del árbol matricial , lo que da lugar a un algoritmo de tiempo polinomial.

El teorema BEST se enuncia por primera vez de esta forma en una "nota añadida a la demostración" del artículo de Aardenne-Ehrenfest y de Bruijn (1951). La demostración original era biyectiva y generalizaba las secuencias de De Bruijn . Es una variación de un resultado anterior de Smith y Tutte (1941).

Contar el número de circuitos eulerianos en grafos no dirigidos es mucho más difícil. Se sabe que este problema es #P-completo . [ 10 ] En una dirección positiva, se cree que un enfoque de Monte Carlo de cadena de Markov , a través de las transformaciones de Kotzig (introducidas por Anton Kotzig en 1968), proporciona una aproximación precisa para el número de circuitos eulerianos en un grafo, aunque hasta ahora no hay prueba de este hecho (ni siquiera para grafos de grado acotado).

Casos especiales

McKay y Robinson (1995) determinaron una fórmula asintótica para el número de circuitos eulerianos en los grafos completos : [ 11 ]

CE⁡(Knorte)=2(norte+1)2π12mi−norte22+1112norte(norte−2)(norte+1)2(1+O(norte−12+ϵ)).{\displaystyle \operatorname {ec} (K_{n})=2^{\frac {(n+1)}{2}}\pi ^{\frac {1}{2}}e^{{\frac {-n^{2}}{2}}+{\frac {11}{12}}}n^{\frac {(n-2)(n+1)}{2}}{\bigl (}1+O(n^{-{\frac) {1}{2}}+\epsilon }){\bigr )}.}

Una fórmula similar fue obtenida posteriormente por MI Isaev (2009) para grafos bipartitos completos : [ 12 ]

CE⁡(Knorte,norte)=(norte2−1)¡2norte2norte2−norte+12π−norte+12nortenorte−1(1+O(norte−12+ϵ)).{\displaystyle \operatorname {ec} (K_{n,n})=\left({\frac {n}{2}}-1\right)!^{2n}2^{n^{2}-n+{\frac {1}{2}}}\pi ^{-n+{\frac {1}{2}}}n^{n-1}{\bigl (}1+O(n^{-{\frac {1}{2}}+\epsilon }){\bigr )}.}

Aplicaciones

Los recorridos eulerianos se utilizan en bioinformática para reconstruir la secuencia de ADN a partir de sus fragmentos. [ 13 ] También se utilizan en el diseño de circuitos CMOS para encontrar un ordenamiento óptimo de las compuertas lógicas . [ 14 ] Existen algunos algoritmos para procesar árboles que se basan en un recorrido euleriano del árbol (donde cada arista se trata como un par de arcos). [ 15 ] [ 16 ] Las secuencias de De Bruijn se pueden construir como recorridos eulerianos de grafos de De Bruijn . [ 17 ]

En grafos infinitos

Un grafo infinito con todos los grados de los vértices iguales a cuatro, pero sin línea euleriana.

En un grafo infinito , el concepto correspondiente a un camino euleriano o ciclo euleriano es una línea euleriana, un camino doblemente infinito que cubre todas las aristas del grafo. No es suficiente para la existencia de tal camino que el grafo sea conexo y que todos los grados de los vértices sean pares; por ejemplo, el grafo infinito de Cayley mostrado, con todos los grados de los vértices iguales a cuatro, no tiene línea euleriana. Los grafos infinitos que contienen líneas eulerianas fueron caracterizados por Erdős, Grünwald y Weiszfeld (1936) . Para que un grafo infinito o multigrafo G tenga una línea euleriana, es necesario y suficiente que se cumplan todas las siguientes condiciones: [ 18 ] [ 19 ]

  • G está conectado.
  • G tiene conjuntos numerables de vértices y aristas.
  • G no tiene vértices de grado impar (finito).
  • Eliminar cualquier subgrafo finito S de G deja como máximo dos componentes conexas infinitas en el grafo restante, y si S tiene grado par en cada uno de sus vértices, entonces al eliminar S queda exactamente una componente conexa infinita.

Grafos eulerianos no dirigidos

Euler enunció una condición necesaria para que un grafo finito sea euleriano: todos sus vértices deben tener grado par. Hierholzer demostró que esta es una condición suficiente en un artículo publicado en 1873. Esto nos lleva a la siguiente afirmación necesaria y suficiente sobre lo que debe tener un grafo finito para ser euleriano: Un grafo finito conexo no dirigido es euleriano si y solo si cada vértice de G tiene grado par. [ 20 ]

Veblen demostró el siguiente resultado en 1912: Un grafo conexo no dirigido es euleriano si y solo si es la unión disjunta de algunos ciclos. [ 20 ]

Un grafo dirigido con todos los grados pares que no es euleriano, sirviendo como contraejemplo a la afirmación de que una condición suficiente para que un grafo dirigido sea euleriano es que tenga todos los grados pares.
Un grafo dirigido con todos los grados pares que no es euleriano, sirviendo como contraejemplo a la afirmación de que una condición suficiente para que un grafo dirigido sea euleriano es que tenga todos los grados pares.

Hierholzer desarrolló un algoritmo de tiempo lineal para construir un recorrido euleriano en un grafo no dirigido.

Grafos eulerianos dirigidos

Es posible tener un grafo dirigido con grados de salida pares que no sea euleriano. Dado que un circuito euleriano sale de un vértice el mismo número de veces que entra en él, una condición necesaria para que exista un circuito euleriano es que el grado de entrada y el grado de salida sean iguales en cada vértice. Obviamente, la conectividad también es necesaria. König demostró que estas condiciones también son suficientes. Es decir, un grafo dirigido es euleriano si y solo si es conexo y el grado de entrada y el grado de salida son iguales en cada vértice. [ 20 ]

En este teorema no importa si "conectado" significa "débilmente conectado" o "fuertemente conectado", ya que son equivalentes para los grafos eulerianos.

El algoritmo de tiempo lineal de Hierholzer para construir un recorrido euleriano también es aplicable a grafos dirigidos. [ 20 ]

Gráficos eulerianos mixtos

Este grafo mixto es euleriano. El grafo es par pero no simétrico, lo que demuestra que la paridad y la simetría no son condiciones necesarias ni suficientes para que un grafo mixto sea euleriano.
Este grafo mixto es euleriano. El grafo es par pero no simétrico, lo que demuestra que la paridad y la simetría no son condiciones necesarias ni suficientes para que un grafo mixto sea euleriano.

Todos los grafos mixtos que son a la vez pares y simétricos tienen garantizada la naturaleza euleriana. Sin embargo, esta no es una condición necesaria, ya que es posible construir un grafo par no simétrico que sea euleriano. [ 20 ]

Ford y Fulkerson demostraron en 1962 en su libro Flows in Networks [ 21 ] una condición necesaria y suficiente para que un grafo sea euleriano, a saber, que cada vértice debe ser par y satisfacer la condición de equilibrio, es decir, para cada subconjunto de vértices S, la diferencia entre el número de arcos que salen de S y entran en S debe ser menor o igual que el número de aristas incidentes con S. [ 20 ]

El proceso de comprobar si un grafo mixto es euleriano es más difícil que comprobar si un grafo no dirigido o dirigido es euleriano, porque la condición de conjunto equilibrado afecta a todos los subconjuntos posibles de vértices.

Ciclos y puentes eulerianos

Un grafo euleriano se define como un grafo con un ciclo euleriano. Todo grafo euleriano es un grafo sin puentes . Esto se debe a que en un grafo euleriano cada arista forma parte de un ciclo euleriano. Por lo tanto, si se elimina una arista, sus extremos permanecen conectados a través del resto del ciclo. Sin embargo, lo contrario no es cierto.

Un grafo casi euleriano se define como aquel que puede convertirse en euleriano añadiéndole una sola arista (o, equivalentemente, un grafo que contiene un camino euleriano). Todo grafo casi euleriano carece casi por completo de puentes, pero lo contrario no es cierto.

Las clases de grafos sin puentes y grafos casi eulerianos tienen una intersección no vacía (los grafos eulerianos son tanto sin puentes como casi eulerianos), pero no se contienen entre sí. [ 22 ] : Apéndice B

Un grafo mixto par que viola la condición de conjunto equilibrado y, por lo tanto, no es euleriano.
Un grafo mixto par que viola la condición de conjunto equilibrado y, por lo tanto, no es euleriano.
Un grafo mixto par que satisface la condición de conjunto equilibrado y, por lo tanto, es un grafo mixto euleriano.
Un grafo mixto par que satisface la condición de conjunto equilibrado y, por lo tanto, es un grafo mixto euleriano.

Véase también

Notas

  1. 1 2 Algunas personas reservan los términos camino y ciclo para referirse a caminos y ciclos que no se autointersectan . Un camino que se autointersecta (potencialmente) se conoce como sendero o recorrido abierto ; y un ciclo que se autointersecta (potencialmente) se conoce como circuito o recorrido cerrado . Esta ambigüedad puede evitarse utilizando los términos sendero euleriano y circuito euleriano cuando se permite la autointersección.

Referencias

  1. ↑ NL Biggs , EK Lloyd y RJ Wilson , Teoría de grafos, 1736–1936 , Clarendon Press, Oxford, 1976, 8–9, ISBN 0-19-853901-0.
  2. ↑ CL Mallows, NJA Sloane (1975). "Los grafos de dos clases, las clases de conmutación y los grafos de Euler son iguales en número" (PDF) . SIAM Journal on Applied Mathematics . 28 (4): 876– 880. doi : 10.1137/0128070 . JSTOR 2100368 . 
  3. ↑ Jun-ichi Yamaguchi, Introducción a la teoría de grafos .
  4. ↑ Esquema de Schaum sobre la teoría y los problemas de la teoría de grafos Por VK Balakrishnan.
  5. ↑ Schrijver, A. (1983), "Límites en el número de orientaciones eulerianas" , Combinatorica , 3 ( 3–4 ): 375–380 , doi : 10.1007/BF02579193 , MR 0729790 , S2CID 13708977  .
  6. 1 2 3 4 Pólya, George ; Tarjan, Robert E .; Woods, Donald R. (octubre de 2009), "Caminos hamiltonianos y eulerianos", Notas sobre combinatoria introductoria , Birkhäuser Boston, págs. 157–168 , doi : 10.1007/978-0-8176-4953-1_13 , ISBN  9780817649531
  7. ↑ Fleury, Pierre-Henry (1883), "Deux problèmes de Géométrie de situación" , Journal de mathématiques élémentaires , 2.ª ser. (en francés), 2 : 257– 261.
  8. ↑ Tarjan, R. Endre (1974), "Una nota sobre cómo encontrar los puentes de un grafo", Information Processing Letters , 2 (6): 160– 161, doi : 10.1016/0020-0190(74)90003-9 , MR 0349483 .
  9. ↑ Fleischner, Herbert (1991), "X.1 Algoritmos para senderos eulerianos", Grafos eulerianos y temas relacionados: Parte 1, Volumen 2 , Anales de matemáticas discretas, vol. 50, Elsevier, pp. X.1–13 , ISBN   978-0-444-89110-5.
  10. ↑ Brightwell y Winkler , " Nota sobre el conteo de circuitos eulerianos ", 2004.
  11. ↑ Brendan McKay y Robert W. Robinson, Enumeración asintótica de circuitos eulerianos en el grafo completo , Combinatorica , 10 (1995), n.º 4, 367–377.
  12. ↑ MI Isaev (2009). "Número asintótico de circuitos eulerianos en grafos bipartitos completos". Actas de la 52.ª Conferencia MFTI (en ruso). Moscú: 111–114 .
  13. ↑ Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001). "Un enfoque de sendero euleriano para el ensamblaje de fragmentos de ADN" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 98 (17): 9748– 9753. Bibcode : 2001PNAS...98.9748P . doi : 10.1073/pnas.171285098 . PMC 55524. PMID 11504945 .  
  14. ↑ Roy, Kuntal (2007). "Ordenación óptima de compuertas lógicas CMOS mediante el enfoque de la ruta de Euler: algunas ideas y explicaciones" . Journal of Computing and Information Technology . 15 (1): 85– 92. doi : 10.2498/cit.1000731 .
  15. ^ Tarjan, Robert E.; Vishkin, Uzi (1985). "Un algoritmo eficiente de biconectividad paralela". Revista SIAM de Computación . 14 (4): 862–874 . CiteSeerX 10.1.1.465.8898 . doi : 10.1137/0214061 . 
  16. ↑ Berkman, Omer; Vishkin, Uzi (abril de 1994). "Finding level-ancestors in trees". J. Comput. Syst. Sci . 2. 48 (2): 214– 230. doi : 10.1016/S0022-0000(05)80002-9 .
  17. ↑ Savage, Carla (enero de 1997). "Un estudio de los códigos Gray combinatorios". SIAM Review . 39 (4): 605– 629. doi : 10.1137/S0036144595295272 . ISSN 0036-1445 . 
  18. ↑ Komjáth, Peter (2013), "El trabajo de Erdős sobre gráficos infinitos" , centenario de Erdös , Bolyai Soc. Matemáticas. Stud., vol. 25, János Bolyai Math. Soc., Budapest, págs. 325– 345, doi : 10.1007/978-3-642-39286-3_11 , MR 3203602   .
  19. ↑ Bollobás, Béla (1998), Teoría moderna de grafos , Textos de posgrado en matemáticas, vol. 184, Springer-Verlag, Nueva York, p. 20, doi : 10.1007/978-1-4612-0619-4 , ISBN   0-387-98488-7, MR 1633290 .
  20. 1 2 3 4 5 6 Corberán, Ángel; Laporte, Gilbert, eds. (2015). Enrutamiento de arcos: problemas, métodos y aplicaciones . Serie MOS-SIAM sobre optimización. SIAM. doi : 10.1137/1.9781611973679 . ISBN 978-1-61197-366-2. Consultado el 19 de agosto de 2022 .
  21. ↑ LR Ford; DR Fulkerson (1962). Flujos en redes . Princeton, NJ: Princeton University Press. ISBN 9780691079622.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
  22. ↑ Bei, Xiaohui; Elkind, Edith; Segal-Halevi, Erel; Suksompong, Warut (2025-03-31). "Dividiendo un pastel gráfico" . SIAM Journal on Discrete Mathematics . 39 (1): 19– 54. arXiv : 1910.14129 . doi : 10.1137/22M1500502 . ISSN 0895-4801 . 

Bibliografía