Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Four- and five-component molecular solids: crystal engineering strategies based on structural inequivalence

A synthetic strategy is described for the co-crystallization of four-and five-component molecular crystals, based on the fact that if any particular chemical constituent of a lower cocrystal is found in two different structural environments, these differences may be exploited to increase the number of components in the solid. 2-Methylresorcinol and tetramethylpyrazine are basic template molecules that allow for further supramolecular homologation. Ten stoichiometric quaternary cocrystals and one quintinary cocrystal with some solid solution character are reported. Cocrystals that do not lend themselves to such homologation are termed synthetic dead ends.