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.

Fire and soil temperatures during controlled burns in seasonally dry tropical forests of southern India

Fire and soil temperatures were measured during controlled burns conducted by the Forest Department at two seasonally dry tropical forest sites in southern India, and their relationships with fuel load, fuel moisture and weather variables assessed using stepwise regression. Fire temperatures at the ground level varied between 79 degrees C and 760 degrees C, with higher temperatures recorded at high fuel loads and ambient temperatures, whereas lower temperatures were recorded at high relative humidity. Fire temperatures did not vary with fuel moisture or wind speed. Soil temperatures varied between <79 degrees C and 302 degrees C and were positively correlated with ground-level fire temperatures. Results from the study imply that fuel loads in forested areas have to be reduced to ensure low intensity fires in the dry season. Low fire temperatures would ensure lower mortality of above-ground saplings and minimal damage to root stocks of tree species that would maintain the regenerative capacity of a tropical dry forest subject to dry season wildfires.