Algorítmica y complejidad computacional. Un caso de A5 (60 vértices) sin osbtrucciones pero con obstáculos.

mayo 23, 2017

1.Estoy poniendo a prueba el método de la escalera con este caso, que que me sirve para testar varios temas:

Leer el resto de esta entrada »

Algorítmica y complejidad computacional. DCBs: Algunos casos ¿ nuevos ? y ¿ difíciles ?.

mayo 21, 2017

He estado releyendo literatura más relacionada con nuestra investigación y he identificado algunos casos nuevos, que en algunos casos los autores señalan como difíciles, y cuyas propiedades estructurales quiero determinar, siempre y cuando esto no me exija reprogramar las implementaciones que ya tengo.

1. Tesis de Effler y/o Shields.

Leer el resto de esta entrada »

Algorítmica y complejidad computacional. DBCs: Novedades.

mayo 20, 2017

Me está pasando una cosa extrañísima: no puedo entrar en mi blog desde ninguno de los ordenadores de mi vivienda, pero sí desde otros (desde un cibercafé).  Ni para editar ni para ver entradas. Los problemas son sólo para entrar en mi blog y en otras páginas de WordPress. Por ejemplo la páginaeffler de acceso al blog. Pero no tengo problemas para entrar en otros blogs de WordPress de terceras personas. Tampoco en otras páginas web. ¿¿??. Es decir la navegación es perfecta excepto para la página de acceso al blog de WordPress. No me explico que puede pasar. He borrado la caché, reseteado el router etc…es decir técnicas que otras veces han funcionado. Lo extraño es que pase con todos los ordenadores de la vivienda y no sólo con el que uso habitualmente.

Actualización mismo día noche: ¡ Solucionado !. Sin hacer yo nada. Otra rareza de internet que no me explico. Y no estoy pensando en ninguna “agresión” dirigida específicamente a mi vivienda. Seguramente ha sido un tema general de wordpress, pero sigo sin entender pq en el ciber si podía acceder… Paso a pulir la entrada. Fin de actualización.

En fin escribo desde un ciber. Por fin he tenido un poco de tiempo para releer entradas anteriores que listamos en una entrada anterior, y antes de que se me complique de nuevo la vida (seguramente dentro de una semana), tengo ya algunos temas completamente claros que son los que quiero publicar en esta entrada muy brevemente. De nuevo me está costando coger ritmo y no se si me va a dar tiempo en una semana a sumergirme lo suficiente en el tema como para obtener resultados tan notables como hace un par de meses más o menos. Como en esa ocasión no publicaremos todo.

Es posible que los comentarios que siguen contengan errores o inexactitudes que corregiremos cuanto tengamos acceso al blog desde el domicilio):

Leer el resto de esta entrada »

Algorítmica y complejidad computacional. Muy breve historia (bibliográfica) de la teoría de grafos.

mayo 15, 2017

La primera versión, corta, de esta entrada se hizo el 15 de  mayo. Se ha actualizado para obtener una versión mas larga con actualizaciones el 16 y 17 de mayo.

Leer el resto de esta entrada »

Algorítmica y complejidad computacional. La teoría y la práctica: isomorfismo de grafos.

mayo 11, 2017

 Tras  un breve paréntesis en el que nos hemos tenido que concentrar en otros temas, retomamos las entradas sobre estos contenidos.

Un artículo interesante sobre isomorfismo de grafos. La teoría es el reciente resultado de Babai. Y también un resultado publicado ayer que demuestra que un método de solución de este problema (obviamente no el de Babai sino al parecer uno de los más utilizados en la práctica) es exponencial peor caso.

An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism

Daniel Neuen and Pascal Schweitzer RWTH Aachen University {neuen,schweitzer}@informatik.rwth-aachen.de

May 10, 2017

Abstract.  The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow this approach. While these solvers are fast in practice, from a theoretical point of view, no general lower bounds concerning the worst case complexity of these tools are known. In fact, it is an open question whether individualization-refinement algorithms can achieve upper bounds on the running time similar to the more theoretical techniques based on a group theoretic approach. In this work we give a negative answer to this question and construct a family of graphs on which algorithms based on the individualization-refinement paradigm require exponential time. Contrary to a previous construction of Miyazaki, that only applies to a specific implementation within the individualization-refinement framework, our construction is immune to changing the cell selector, or adding various heuristic invariants to the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case when the k-dimensional Weisfeiler-Leman algorithm is used to replace the standard color refinement operator and the arguments even work when the entire automorphism group of the inputs is initially provided to the algorithm.

Extracto.  There are several highly efficient isomorphism software packages implementing the paradigm. Among them are nauty/traces [15], bliss [11], conauto [13] and saucy [6]. While they all follow the basic individualization-refinement paradigm, these algorithms differ drastically in design principles and algorithmic realization. In particular, they differ in the way the search tree is traversed, they use different low level subroutines, have diverse ways to perform tasks such as automorphism detection, and they use different cell selection strategies as well as vertex invariants and refinement operators.

With Babai’s [2] recent quasi-polynomial time algorithm for the graph isomorphism problem, the theoretical worst case complexity of algorithms for the graph isomorphism problem was drastically improved from a previous best e O( √ n log n) (see [3]) to O(n logc n ) for some constant c ∈ N. As an open question, Babai asks [2] for the worst case complexity of algorithms based on individualizationrefinement techniques. About this worst case complexity, very little had been known. In 1995 Miyazaki [16] constructed a family of graphs on which the then current implementation of nauty has exponential running time. For this purpose these graphs are designed to specifi- cally fool the cell selection process into exponential behavior. However, as Miyazaki also argues, with a different cell selection strategy the examples can be solved in polynomial time within the individualization-refinement paradigm. In this paper we provide general lower bounds for individualization-refinement algorithms with arbitrary combinations of cell selection, refinement operators, invariants and even given perfect automorphism pruning. More precisely, the graphs we provide yield an exponential size search tree (i.e., 2 Ω(n) nodes) for any combination of refinement operator, invariants, and the cell selector which are not stronger than the k-dimensional Weisfeiler-Leman algorithm for some fixed dimension k. The natural class of algorithms for which we thus obtain lower bounds encompasses all software packages mentioned above even with various combinations of switches that can be turned on and off in the execution of the algorithm to tune the algorithms towards specific input graphs. Our graphs are asymmetric, i.e., have no non-trivial automorphisms, and thus no strategy for automorphism detection can help the algorithm to circumvent the exponential lower bound.

En el segundo paper nos informan sobre el estado del arte de la práctica tras este resultado.

 Benchmark Graphs for Practical Graph Isomorphism Daniel Neuen and Pascal Schweitzer

May 11, 2017

Abstract The state-of-the-art solvers for the graph isomorphism problem can readily solve generic instances with tens of thousands of vertices. Indeed, experiments show that on inputs without particular combinatorial structure the algorithms scale almost linearly. In fact, it is non-trivial to create challenging instances for such solvers and the number of difficult benchmark graphs available is quite limited. We describe a construction to efficiently generate small instances for the graph isomorphism problem that are difficult or even infeasible for said solvers. Up to this point the only other available instances posing challenges for isomorphism solvers were certain incidence structures of combinatorial objects (such as projective planes, Hadamard matrices, Latin squares, etc.). Experiments show that starting from 1500 vertices our new instances are several orders of magnitude more difficult on comparable input sizes. More importantly, our method is generic and efficient in the sense that one can quickly create many isomorphism instances on a desired number of vertices. In contrast to this, said combinatorial objects are rare and difficult to generate and with the new construction it is possible to generate an abundance of instances of arbitrary size. Our construction hinges on the multipedes of Gurevich and Shelah and the Cai-FürerImmerman gadgets that realize a certain abelian automorphism group and have repeatedly played a role in the context of graph isomorphism. Exploring limits of such constructions, we also explain that there are group theoretic obstructions to generalizing the construction with non-abelian gadgets.

Extractos.

The practical algorithms underlying these solvers differ from the ones employed to obtain theoretical results. Indeed, there is a big disconnect between theory and practice [2]. One could 1 interpret Babai’s recent breakthrough, the quasipolynomial time algorithm [1], as a first step of convergence. The result implies that if graph isomorphism is NP-complete then all problems in NP have quasi-polynomial time algorithms, which may lead one to also theoretically believe that graph isomorphism is not NP-complete.

P.s. Otro paper que no tiene nada que ver con el anterior pero que nos  ha parecido interesante.

 A Survey of Shortest-Path Algorithms

Amgad Madkour1 , Walid G. Aref1 , Faizan Ur Rehman2 , Mohamed Abdur Rahman2 , Saleh Basalamah2 1 Purdue University, West Lafayette, USA 2 Umm Al-Qura University, Makkah, KSA

May 8, 2017

Abstract. A shortest-path algorithm finds a path containing the minimal cost between two vertices in a graph. A plethora of shortest-path algorithms is studied in the literature that span across multiple disciplines. This paper presents a survey of shortest-path algorithms based on a taxonomy that is introduced in the paper. One dimension of this taxonomy is the various flavors of the shortest-path problem. There is no one general algorithm that is capable of solving all variants of the shortest-path problem due to the space and time complexities associated with each algorithm. Other important dimensions of the taxonomy include whether the shortest-path algorithm operates over a static or a dynamic graph, whether the shortest-path algorithm produces exact or approximate answers, and whether the objective of the shortest-path algorithm is to achieve time-dependence or is to only be goal directed. This survey studies and classifies shortest-path algorithms according to the proposed taxonomy. The survey also presents the challenges and proposed solutions associated with each category in the taxonomy

Trade Lane Megacities. La Ruta del Norte, caliente.

mayo 11, 2017

Hace tiempo que no tratamos este tema. Un artículo reciente.

Trade Lane Megacities. Paraguay, potencia mundial en transporte de mercancías…¡¡ por agua !!

mayo 9, 2017

Nota inicial. Estamos preparando una entrada con estadísticas básicas de navegación mercante fluvial, parecida a la entrada sobre transporte aéreo. Ya tenemos algunos documentos interesantes. Esta entrada es sólo un avance. Fin de nota.

“Somos la primera flota fluvial de Sudamérica lejos, Paraguay tiene casi 4 mil barcazas cuando Brasil no llega a 300 y Argentina no supera las 100, Colombia está intentando recuperar la navegación en el río magdalena realizando una logística distinta aunque le llevaría años alcanzar el nivel que tenemos en Paraguay y todo lo que hemos logrado y construido en los últimos años”

Fuente (2016).

A efectos comparativos, Holanda, primera potencia fluvial europea tiene unas 5000 barcazas.

Fuente (Atlas of the Rivers of the world: The Rivers of the World Atlas has been developed by NEA in close cooperation with EICB and Marin in assignment of the Netherlands Ministry of Economic Affairs, Agriculture and Innovation/NL EVD International. It is presented at the Rivers of the World Forum: a Dutch initiative to stimulate inland navigation all over the world).  Este es uno de los documentos interesantes que he encontrado, con múltiples datos sobre navegación fluvial (mapas y estadísticas, en particular la cuota de transporte doméstico por modo, dato que estábamos buscando) en los principales ríos del mundo.

En navegación fluvial de momento destacan dos ríos: Misisipi y Yangtzé. Los dos pertenecen a una sola nació. Otros sistemas, ya internacionales muy dinámicos son el Rin (según determinados parámetros el más navegado pese a que por sus dimensiones no es comparable a otros),  sobre el que hemos hablado en una entrada anterior y el sistema Paraguay-Paraná sobre el que estamos hablando en parte en ésta. Los países del Rhin (nos olvidamos de Suiza que entiendo aporta poco a su navegación) pertenecen a la UE, que es un bloque económico muy integrado). Y lo mismo se puede decir del sistema Parana-Paraguay y el Mercosur.

De esta forma Paraguay cuenta actualmente con la 3ª flota fluvial a nivel mundial después de EE.UU. y China con 2.200 barcazas y 200 remolcadores e incluye además barcazas para el transporte de líquidos, hidrocarburos y gases.

Fuente (¿2011?).

Este dato no cuadra del todo con los dos anteriores. El problema puede estar en las fechas.

A través de Paraguay se canaliza gran parte de la producción de commodities del heartland de Latam del Sur (destaca la elevada producción de soja en toda la zona). Hay que explicar como Paraguay ha conseguido capturar este mercado de transporte ya que  no es el único país atravesado por la hidrovía Paraná-Paraguay, sobre la que hablaremos en otra entrada (es una vía internacional, que a las dificultades técnicas de gestión, añade las políticas).  En Europa el país que lo ha capturado está en la desembocadura.

P.s. Recomendamos a los lectores leer estas dos entradas sobre unidades de medida de transporte. La tonelada-kilómetro es especialmente útil tal y como nos explican en la entrada en francés.

Unidades de medida para el transporte.

Toneladas-kilometros.

 

 

 

Trade Lane Megacities. Civilizaciones prístinas: lo Mesoaméricano, lo Andino, lo Mesopotámico.

mayo 7, 2017

Disclaimer. Obviamente en esta entrada como en todas las anteriores solo reflejamos nuestras propias opiniones y en ningún caso las de las entidades con las que podamos colaborar.

Con esta entrada continuamos una temática sobre civilizaciones prístinas que ya hemos abordado en varias entradas anteriores hace varios meses. Ver por ejemplo esta entrada.

Hasta la época de la navegación interoceánica atlántica, las civilizaciones americanas son las únicas sobre las que, sin lugar a dudas, se pueden afirmar que tuvieron un desarrollo prístino. Otros casos euroasiáticos están menos claros.

Es interesante ver cuales fueron sus desarrollos y cuales eran sus limitaciones.  En esta entrada nos centramos principalmente en el impacto del pastoralismo en el desarrollo de una civilización.

Espero que no se interprete esta entrada como otro ejercicio de narcisismo  euroasiático. No  lo es. Y tampoco es un ejercicio de hagiografía indigenista.

Sólo intentamos en la medida de lo posible un estudio lo más objetivo y documentado posible de las civilizaciones prístinas.

Leer el resto de esta entrada »

Trade Lane Megacities. Ranking de empresas de transporte aéreo (toneladas transportadas).

mayo 6, 2017
  1. Estado actual. En una entrada anterior nos preguntábamos sobre el estado del transporte de carga aéreo (siempre nos hemos centrado más en el transporte de carga marítimo). En este entrada presentamos unos breves datos al respecto. Aquí se pueden ver las 50 primeras compañías de transporte de carga aéreo. Los extractos son de este muy interesante informe de Boeing, titulado World Air Cargo Forecast.

La carga transportada por estas 50 primeras compañías supone el 90% de la carga aérea total.

Las dos primeras, Federal Express (FedEx) y United Parcel Service (UPS) son especialistas y originadas, como no en EEUU. La tercera es Emirates.

La primera, Federal Express transporta unos 7 millones de toneladas al año.

Hay un total de 1770 aviones

Leer el resto de esta entrada »

Trade Lane Megacities. El boomerang centro-europeo.

mayo 5, 2017

1.Una ciudad, una megaciudad, es producto de una acción colectiva descoordinada y más o menos regulada. La regulación casi siempre es posterior a la acción colectiva espontánea que hace que por diversos motivos, en general económicos, los actores sociales se concentren en determinadas zonas. A veces la regulación acompaña bien la tendencia espontánea al crecimiento, a veces la limita o incluso la elimina.

En la serie Trade Lane Megacities estamos estudiando, intentando explicar las acciones colectivas urbanísticas contemporáneas. Desde hace años hemos estudiado el impacto de las rutas marítimas mercantes sobre esta acción colectiva urbana. Manejamos la hipótesis que la población tenderá a desplazarse al entorno de los nodos principales de lo que hemos llamado Ruta Central. En estos nodos se da un urbanismo muy particular, vanguardia cultural actual.

Leer el resto de esta entrada »