Novel techniques for automorphism group computation

Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. In this work we propose four novel techniques to speed up algorithms that solve the GA problem by exploring a search tree. They increase the performance of the algorithm by allowing to reduce the depth of the search tree, and by effectively pruning it. We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of the input graph. We also describe how the techniques have been incorporated into the GA algorithm conauto, as conauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity. We have experimentally evaluated the impact of each of the above techniques with several graph families. We have observed that each of the techniques by itself significantly reduces the number of processed nodes of the search tree in some subset of graphs, which justifies the use of each of them. Then, when they are applied together, their effect is combined, leading to reductions in the number of processed nodes in most graphs. This is also reflected in a reduction of the running time, which is substantial in some graph families.

Technical Challenges in the Construction of Gothic Vaults: The Gothic Theory of Structural Design

The construction of a Gothic vault implied the solution of several technical challenges. The literature on Gothic vault construction is quite large and its growth continues steadily. The main challenge of any structure is that, during and after construction, it must be "safe", that is, it must not collapse. Indeed, it must be amply safe, able to support different loads for long periods of time. Masonry architecture has shown its structural safety for centuries or millennia. The Pantheon of Rome stands today after almost 2,000 years without having needed any structural reinforcement (of course, the survival of any building implies continuous maintenance) . Hagia Sophia in Istanbul, finished in the 6th century AD, has withstood not only the dead loads but also many severe earthquakes . Finally, the Gothic cathedrals, with their appearance of weakness, are• more than a half millennium old. The question arises of what the source of this amazing strength is and how the illiterate master masons were able to design such daring and safe structures . This question is usually evaded in manuals of Gothic architecture. This is quite surprising, the structure being a fundamental part of Gothic buildings. The present article aims to give such an explanation, which has been studied in detail elsewhere. In the first part, the Gothic design methods "V ill be discussed. In the second part, the validity of these methods wi11 be verified within the frame of the modern theory of masonry structures . References have been reduced to a minimum to make the text simpler and more direct.

Distributed orientation agreement in a group of robots

In this article, a method for the agreement of a set of robots on a common reference orientation based on a distributed consensus algorithm is described. It only needs that robots detect the relative positions of their neighbors and communicate with them. Two different consensus algorithms based on the exchange of information are proposed, tested and analyzed. Systematic experiments were carried out in simulation and with real robots in order to test the method. Experimental results show that the robots are able to agree on the reference orientation under certain conditions. Scalability with an increasing number of robots was tested successfully in simulation with up to 49 robots. Experiments with real robots succeeded proving that the proposed method works in reality.

Distributed Orientation Agreement in a Group of Robots

In this article, a method for the agreement of a set of robots on a common reference orientation based on a distributed consensus algorithm is described. It only needs that robots detect the relative positions of their neighbors and communicate with them. Two different consensus algorithms based on the exchange of information are proposed, tested and analyzed. Systematic experiments were carried out in simulation and with real robots in order to test the method. Experimental results show that the robots are able to agree on the reference orientation under certain conditions. Scalability with an increasing number of robots was tested successfully in simulation with up to 49 robots. Experiments with real robots succeeded proving that the proposed method works in reality.

Spatial analysis of geometric design consistency and road sight distance

Because of the high number of crashes occurring on highways, it is necessary to intensify the search for new tools that help in understanding their causes. This research explores the use of a geographic information system (GIS) for an integrated analysis, taking into account two accident-related factors: design consistency (DC) (based on vehicle speed) and available sight distance (ASD) (based on visibility). Both factors require specific GIS software add-ins, which are explained. Digital terrain models (DTMs), vehicle paths, road centerlines, a speed prediction model, and crash data are integrated in the GIS. The usefulness of this approach has been assessed through a study of more than 500 crashes. From a regularly spaced grid, the terrain (bare ground) has been modeled through a triangulated irregular network (TIN). The length of the roads analyzed is greater than 100 km. Results have shown that DC and ASD could be related to crashes in approximately 4% of cases. In order to illustrate the potential of GIS, two crashes are fully analyzed: a car rollover after running off road on the right side and a rear-end collision of two moving vehicles. Although this procedure uses two software add-ins that are available only for ArcGIS, the study gives a practical demonstration of the suitability of GIS for conducting integrated studies of road safety.