Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Structural Evolution and Phase Stability of Hume-Rothery Phase in a Mechanically Driven Nanostructured Ag-15 at. pct Sn Alloy

The paper reports phase evolution in mechanically driven Ag-15 at. pct Sn alloy powder starting with elemental powders in order to establish the feasibility of designing nanocomposites of a Ag-Sn solid solution. This alloy lies in the phase field of the hexagonal zeta-phase which is a well-known Hume-Rothery electron compound with an electron-to-atom ratio of about 1.45 and hexagonal crystal structure (a = 0.2966 nm, c = 0.4782 nm). Through a systematic use of X-ray diffraction and transmission electron microscopy, the results establish the formation of the zeta-phase which co-exists with the Ag solid solution during the initial phase of milling. Mechanical milling for long duration (55 hours) destabilizes the zeta-phase. A complete solid solution of Ag with a grain size of similar to 8 nm could be achieved after 60 hours of milling. Additional milling can induce decomposition of the solid solution that results in a reappearance of zeta-phase. We present a detailed thermodynamic calculation which indicates that complete Ag solid solution of the present alloy composition would be possible if the crystallites size can be reduced below a certain critical size. In particular, we show that both Ag and zeta-phase grain sizes need to be taken into account for determining the metastable equilibrium and the phase change that has been experimentally observed. Finally, we argue that recrystallization processes set a limit to the achievable size of the nanoparticles with metastable Ag solid solution.