An O(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn).All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Decision tree design and applications in speech processing

The design and operation of the minimum cost classifier, where the total cost is the sum of the measurement cost and the classification cost, is computationally complex. Noting the difficulties associated with this approach, decision tree design directly from a set of labelled samples is proposed in this paper. The feature space is first partitioned to transform the problem to one of discrete features. The resulting problem is solved by a dynamic programming algorithm over an explicitly ordered state space of all outcomes of all feature subsets. The solution procedure is very general and is applicable to any minimum cost pattern classification problem in which each feature has a finite number of outcomes. These techniques are applied to (i) voiced, unvoiced, and silence classification of speech, and (ii) spoken vowel recognition. The resulting decision trees are operationally very efficient and yield attractive classification accuracies.

A tropical oviparous lizard, Calotes versicolor, exhibiting a potentially novel FMFM pattern of temperature-dependent sex determination

Among squamate reptiles, lizards exhibit an impressive array of sex-determining modes viz. genotypic sex determination, temperature-dependent sex determination, co-occurrence of both these and those that reproduce parthenogenetically. The oviparous lizard, Calotes versicolor, lacks heteromorphic sex chromosomes and there are no reports on homomorphic chromosomes. Earlier studies on this species presented little evidence to the sex-determining mechanism. Here we provide evidences for the potential role played by incubation temperature that has a significant effect (P<0.01) on gonadal sex and sex ratio. The eggs were incubated at 14 different incubation temperatures. Interestingly, 100% males were produced at low (25.5 +/- 0.5 degrees C) as well as high (34 +/- 0.5 degrees C) incubation temperatures and 100% females were produced at low (23.5 +/- 0.5 degrees C) and high (31.5 +/- 0.5 degrees C) temperatures, clearly indicating the occurrence of TSD in this species. Sex ratios of individual clutches did not vary at any of the critical male-producing or female-producing temperatures within as well as across the seasons. However, clutch sex ratios were female- or male-biased at intermediate temperatures. Thermosensitive period occurred during the embryonic stages 3033. Three pivotal temperatures operate producing 1:1 sex ratio. Histology of gonad and accessory reproductive structures provide additional evidence for TSD. The sex-determining pattern, observed for the first time in this species, that neither compares to Pattern I [Ia (MF) and Ib (FM)] nor to Pattern II (FMF), is being referred to as FMFM pattern of TSD. This novel FMFM pattern of sex ratio exhibited by C. versicolor may have an adaptive significance in maintaining sex ratio. J. Exp. Zool. 317:3246, 2012. (c) 2011 Wiley Periodicals, Inc.

Some characteristics of tropical lightning

An integrated and generalized account of the characteristics of lightning flashes observed in the tropics is presented, along with features of tropical lightning which differ from flashes at other latitudes. Several years of lightning recordings were made at two locations in India by using the electromagnetic radiation of the flash in a suitable radio band. The distances of thunder audibility, the number of thunders/hr, the peak flash rate, the flash duration, the time interval between flashes, the duration of flashing activity of a cloud, the number of cells in the lifetime of the cloud, etc. were all found to follow log-normal distributions. Fewer cells were observed to occur in temperate regions, and thunder was found to be associated with ground flashes only.

Vegetative phenology of tropical montane forests in the Nilgiris, South India

Spatial and temporal variation in foliar phenology plays a significant role in growth and reproduction of a plant species. Foliar phenology is strongly influenced by environmental factors such as rainfall. A study on phenology of tropical montane forests was undertaken in three different forest patches of the Nilgiri Mountains in peninsular India above 2000 meters ASL. Since August 2000, 500 trees belonging to 70 species of angiosperms were monitored for both vegetative and reproductive phenologies on a monthly basis. Climate data were collected from nearby weather stations. This paper reports results of the study from August 2000 - August 2003 on foliar phenology. Non-parametric correlations and multiple regressions were performed to analyse the influence of environmental factors such as rainfall, temperature and sunshine on foliar phenology. It was found that moisture related factors had a negative influence on the leaf initiation. Circular statistical analyses were performed to understand the seasonality in different phenophases of foliar phenology. Different phenophases of leafing were not significantly seasonal. Results are discussed and compared among three different forest patches on the Nilgiri plateau and also with other montane forest patches across the globe.

Analysis of residual tropical cemented soil behaviour

In -situ soils in gee-material spectrum might arise due to sedimentation or could be non-sedimentary residual formations. The inherent nature and diversity of geological processes involved in the soil formation stage itself are responsible for a wide variability in the in-situ state of the soil. In this paper the possibility of analyses to arrive at engineering parameters of residual soils with varied degrees of residual or acquired cementation by the use of physical and in-situ parameters normally determined in routine investigations, are examined. An Intrinsic State Line,(ISL), with reference to an intrinsic state parameter (e/e(L)) and its variation with effective stress for reconstituted clays has been developed for residual tropical soils of non-sedimentary origin. In relation to the Intrinsic State Line (ISL), the undisturbed state, e, the potential parameter, e(L), along with the overburden pressure data has been analyzed to identify the dominance of cementation or stress history or both in controlling the compressibility and strength behaviour of natural residual soil. The location of yield stress point in relation to the ISL, pre-, and post- yield stress, compression indices along the e- log sigma(v) path provide a simple means to the analysis of the compressibility characteristics of cemented soils for analysis.

Geometric Decision Tree

In this paper, we present a new algorithm for learning oblique decision trees. Most of the current decision tree algorithms rely on impurity measures to assess the goodness of hyperplanes at each node while learning a decision tree in top-down fashion. These impurity measures do not properly capture the geometric structures in the data. Motivated by this, our algorithm uses a strategy for assessing the hyperplanes in such a way that the geometric structure in the data is taken into account. At each node of the decision tree, we find the clustering hyperplanes for both the classes and use their angle bisectors as the split rule at that node. We show through empirical studies that this idea leads to small decision trees and better performance. We also present some analysis to show that the angle bisectors of clustering hyperplanes that we use as the split rules at each node are solutions of an interesting optimization problem and hence argue that this is a principled method of learning a decision tree.

Does acoustic adaptation drive vertical stratification? A test in a tropical cricket assemblage

In species-rich assemblages, differential utilization of vertical space can be driven by resource availability. For animals that communicate acoustically over long distances under habitat-induced constraints, access to an effective transmission channel is a valuable resource. The acoustic adaptation hypothesis suggests that habitat acoustics imposes a selective pressure that drives the evolution of both signal structure and choice of calling sites by signalers. This predicts that species-specific signals transmit best in native habitats. In this study, we have tested the hypothesis that vertical stratification of calling heights of acoustically communicating species is driven by acoustic adaptation. This was tested in an assemblage of 12 coexisting species of crickets and katydids in a tropical wet evergreen forest. We carried out transmission experiments using natural calls at different heights from the forest floor to the canopy. We measured signal degradation using 3 different measures: total attenuation, signal-to-noise ratio (SNR), and envelope distortion. Different sets of species supported the hypothesis depending on which attribute of signal degradation was examined. The hypothesis was upheld by 5 species for attenuation and by 3 species each for SNR and envelope distortion. Only 1 species of 12 provided support for the hypothesis by all 3 measures of signal degradation. The results thus provided no overall support for acoustic adaptation as a driver of vertical stratification of coexisting cricket and katydid species.

Controls on intense silicate weathering in a tropical river, southwestern India

The Silicate Weathering Rate (SWR) and associated Carbon dioxide Consumption Rate (CCR) in tropical silicate terrain is assessed through a study of the major ion chemistry in a small west flowing river of Peninsular India, the Nethravati River. The specific features of the river basin are high mean annual rainfall and temperature, high runoff and a Precambrian basement composed of granitic-gneiss, charnockite and minor metasediments. The water samples (n = 56) were collected from three locations along the Nethravati River and from two of its tributaries over a period of twelve months. Chemical Weathering Rate (CWR) for the entire watershed is calculated by applying rainwater correction using river chloride as a tracer. Chemical Weathering Rate in the Nethravati watershed is estimated to 44 t.km(-2).y(-1) encompassing a SWR of 42 t.km(-2).y(-1) and a maximum carbonate contribution of 2 t.km(-2).y(-1). This SWR is among the highest reported for granito-gneissic terrains. The assessed CCR is 2.9 . 10(5) mol.km(-2).y(-1). The weathering index (Re). calculated from molecular ratios of dissolved cations and silica in the river, suggests an intense silicate weathering leading to kaolinite-gibbsite precipitation in the weathering covers. The intense SWR and CCR could be due to the combination of high runoff and temperature along with the thickness and nature of the weathering cover. The comparison of silicate weathering fluxes with other watersheds reveals that under similar morpho-climatic settings basalt weathering would be 2.5 times higher than the granite-gneissic rocks. (C) 2012 Elsevier B.V. All rights reserved.

Phylogeny of the Asian Eutropis (Squamata: Scincidae) reveals an `into India' endemic Indian radiation

Recent generic rearrangement of the circumtropical distributed skink genus `Mabuya' has raised a lot of debate. According to this molecular phylogeny based rearrangement, the tropical Asian members of this genus have been assigned to Eutropis. However, in these studies the Asian members of `Mabuya' were largely sampled from Southeast (SE) Asia with very few species from Indian subcontinent. To test the validity of this assignment and to determine the evolutionary origin of Indian members of this group we sequenced one nuclear and two mitochondrial genes from most of the species from the Indian subregion. The nuclear and mitochondrial trees generated from these sequences confirmed the monophyly of the tropical Asian Eutropis. Furthermore, in the tree based on the combined mitochondrial and nuclear dataset an endemic Indian radiation was revealed that was nested within a larger Asian clade. Results of dispersal-vicariance analysis and molecular dating suggested an initial dispersal of Eutropis from SE Asia into India around 5.5-17 million years ago, giving rise to the extant members of the endemic Indian radiation. This initial dispersal was followed by two back dispersals from India into SE Asia. We also discuss the relationships within the endemic Indian radiation and its taxonomic implications. (c) 2012 Elsevier Inc. All rights reserved.

Females of a tree cricket prefer larger males but not the lower frequency male calls that indicate large body size

In the tree cricket Oecanthus henryi, females are attracted by male calls and can choose between males. To make a case for female choice based on male calls, it is necessary to examine male call variation in the field and identify repeatable call features that are reliable indicators of male size or symmetry. Female preference for these reliable call features and the underlying assumption behind this choice, female preference for larger males, also need to be examined. We found that females did prefer larger males during mating, as revealed by the longer mating durations and longer spermatophore retention times. We then examined the correlation between acoustic and morphological features and the repeatability of male calls in the field across two temporal scales, within and across nights. We found that carrier frequency was a reliable indicator of male size, with larger males calling at lower frequencies at a given temperature. Simultaneous playback of male calls differing in frequency, spanning the entire range of natural variation at a given temperature, revealed a lack of female preference for low carrier frequencies. The contrasting results between the phonotaxis and mating experiments may be because females are incapable of discriminating small differences in frequency or because the change in call carrier frequency with temperature renders this cue unreliable in tree crickets. (C) 2012 The Association for the Study of Animal Behaviour. Published by Elsevier Ltd. All rights reserved.