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.

Revalidation of Natrix clerki Wall, 1925, an overlooked species in the genus Amphiesma Dumeril, Bibron & Dumeril, 1854 (Squamata: Natricidae)

Natrix clerki Wall, 1925, previously known from its sole holotype and considered a synonym of Amphiesma parallelum (Boulenger, 1890), is resurrected in the genus Amphiesma on the basis of the analysis of morphological variation in 28 specimens of ``Amphiesma parallelum'' auctorum, plus six living, unvouchered specimens discovered in Arunachal Pradesh and Nagaland, India, and one vouchered specimen from Talle Valley in Arunachal Pradesh. Specimens from northeast India (Nagaland), northern Myanmar, and China (Yunnan), previously identified as Amphiesma parallelum either in the literature or in museum's catalogues, are also here referred to A. clerki. The holotype of Amphiesma clerki is redescribed. As a consequence, the definition of Amphiesma parallelum is modified. A. parallelum inhabits the Khasi Hills and Naga Hills in Northeast India, whereas A. clerki has a wider range in the Eastern Himalayas, northern Myanmar and Yunnan (China). Amphiesma clerki differs from A. parallelum by its longer tail, dorsal scales more strongly keeled, scales of the first dorsal scale row strongly keeled vs. smooth, a postocular streak not interrupted at the level of the neck, and a much more vivid pattern on a darker background colour. Characters of species of the Amphiesma parallelum group, i.e. A. clerki, A. parallelum, A. bitaeniatum, A. platyceps and A. sieboldii are compared. A key to this group is provided.