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.

The knight of sugar industry: T. S. Venkatraman (1884-1963)

Tiruvadi Sambasiva Venkatraman (TSV) was a plant breeder. In response to a call from Pundit Madan Mohan Malaviya, he made it his mission to develop high-yielding varieties of sugarcane for manufacturing sugar and making it available as a sweetening agent and an energy source for the malnourished children of India. Using Saccharum officinarum, then under cultivation in India, as the female parent, he artificially fertilized it with pollen from S. barberi, which grew wild in Coimbatore. After 4-5 recurrent backcrossings of S. officinarum Chi wild Sorghum spontaneum with S. officinarum as the female parent, TSV selected the `rare' interspecies hybrid cane varieties that resembled sugarcane and had approximately 2.5 cm thick juicy stems containing 16-18% sucrose - nearly 35 times more than what occurred in parent stocks. The hybrid canes matured quickly, were resistant to waterlogging, drought, and to the red-rot disease caused by Glomerella tucumanensis (Sordariomycetes: Glomerellaceae), and to the sereh-virus disease. Most importantly, they were amenable for propagation using stem cuttings. In recognition of the development of high-yielding sugarcane varieties, TSV was conferred the titles Rao Bahadur, Rao Sahib, and Sir by the British Government, and Padma Bhushan by the Republic of India. In the next few decades, consequent to TSV's work, India turned into the second largest sugar producer in the world, after Brazil. The hybrid sugarcane varieties developed are the foundational stocks for new sugarcane x bamboo hybrids, and for possible resistance to Puccinia megalocephala (Pucciniomycetes: Pucciniaceae) and Ustilago scitaminea (Ustilaginomycetes: Ustilaginaceae) using molecular techniques.