Optimal radio labellings of complete m-ary trees

A radio labelling of a connected graph G is a mapping f : V (G) → {0, 1, 2, ...} such that | f (u) - f (v) | ≥ diam (G) - d (u, v) + 1 for each pair of distinct vertices u, v ∈ V (G), where diam (G) is the diameter of G and d (u, v) the distance between u and v. The span of f is defined as max_u, _{v ∈ V (G)} | f (u) - f (v) |, and the radio number of G is the minimum span of a radio labelling of G. A complete m-ary tree (m ≥ 2) is a rooted tree such that each vertex of degree greater than one has exactly m children and all degree-one vertices are of equal distance (height) to the root. In this paper we determine the radio number of the complete m-ary tree for any m ≥ 2 with any height and construct explicitly an optimal radio labelling.

The effects of topological inaccuracy in evolutionary trees on the phylogenetic comparative method of independent contrasts

Computer simulations were used to test the effect of increasing phylogenetic topological inaccuracy on the results obtained from correlation tests of independent contrasts. Predictably, increasing the number of disruptions in the tree increases the likelihood of significant error in the r values produced and in the statistical conclusions drawn from the analysis. However, the position of the disruption in the tree is important: Disruptions closer to the tips of the tree have a greater effect than do disruptions that are close to the root of the tree. Independent contrasts derived from inaccurate topologies are more likely to lead to erroneous conclusions when there is a true significant relationship between the variables being tested (i.e., they tend to be conservative). The results also suggest that random phylogenies perform no better than nonphylogenetic analyses and, under certain conditions, may perform even worse than analyses using raw species data. Therefore, the use of random phylogenies is not beneficial in the absence of knowledge of the true phylogeny.

Minimum spanning trees for valley and ridge characterization in digital elevation maps

Texture synthesis employs neighbourhood matching to generate appropriate new content. Terrain synthesis has the added constraint that new content must be geographically plausible. The profile recognition and polygon breaking algorithm (PPA) [Chang et al. 1998] provides a robust mechanism for characterizing terrain as systems of valley and ridge lines in digital elevation maps. We exploit this to create a terrain characterization metric that is robust, efficient to compute and is sensitive to terrain properties.

Terrain regions are characterized as a minimum spanning tree derived from a graph created from the sample points of the elevation map which are encoded as weights in the edges of the graph. This formulation allows us to provide a single consistent feature definition that is sensitive to the pattern of ridges and valleys in the terrain Alternative formulations of these weights provide richer characteristicmeasures and we provide examples of alternate definitions based on curvature and contour measures.

We show that the measure is robust, with a significant portion derived directly from information local to the terrain sample. Global terrain characteristics introduce the issue of over- and underconnected valley/ridge lines when working with sub-regions. This is addressed by providing two graph construction strategies, which respectively provide an upper bound on connectivity as a single spanning tree, and a lower bound as a forest of trees.

Efficient minimum spanning tree algorithms are adapted to the context of terrain data and are shown to provide substantially better performance than previous PPA implementations. In particular, these are able to characterize valley and ridge behaviour at every point even in large elevation maps, providing a measure sensitive to terrain features at all scales.

The resulting graph based formulation provides an efficient and elegant algorithm for characterizing terrain features. The measure can be calculated efficiently, is robust under changes of neighbourhood position, size and resolution and the hybrid measure is sensitive to terrain features both locally and globally.

Involvement of rootstocks and their hydraulic conductance in the drought resistance of grafted rubber trees

Improving drought resistance of rubber trees has become a pressing issue with the extension of rubber plantations and the prevalence of seasonal drought. Root system is vital to water and nutrients uptake of all plants, therefore, rootstocks could play decisive roles in drought resistance of grafted rubber trees on a specific scion clone. To investigate the responses of different clone rootstocks and their grafted trees to water stress and find applicable methods for selecting drought resistant rootstocks, seven related parameters and root hydraulic properties of both seeds originated and grafted saplings of PB86, PR107, RRIM600 and GT1 were measured to assess their drought resistance. It was shown that the rootstock drought resistance and root hydraulic conductance may improve the drought resistance of the grafted rubber trees. Among the four clone rootstocks, GT1, which demonstrated more resistant to drought and higher root hydraulic conductance, was comparatively resistant to drought both for the seed propagation seedlings and grafted saplings. In addition, studies on the grafted saplings with different root hydraulic conductance further validated the possibility of selecting drought resistant rootstocks on the basis of rootstock hydraulic conductance using a high-pressure flow meter.

Extracting common subtrees from decision trees

This paper explores an efficient technique for the extraction of common subtrees in decision trees. The method is based on a Suffix Tree string matching process and the algorithm is applied to the problem of finding common decision rules in path planning.

Video indexing and similarity retrieval by largest common subgraph detection using decision trees

While the largest common subgraph (LCSG) between a query and a database of models can provide an elegant and intuitive measure of similarity for many applications, it is computationally expensive to compute. Recently developed algorithms for subgraph isomorphism detection take advantage of prior knowledge of a database of models to improve the speed of on-line matching. This paper presents a new algorithm based on similar principles to solve the largest common subgraph problem. The new algorithm significantly reduces the computational complexity of detection of the LCSG between a known database of models, and a query given on-line.

Bayesian networks and decision trees in the diagnosis of female urinary incontinence

This study compares the effectiveness of Bayesian networks versus Decision Trees in modeling the Integral Theory of Female Urinary Incontinence diagnostic algorithm. Bayesian networks and Decision Trees were developed and trained using data from 58 adult women presenting with urinary incontinence symptoms. A Bayesian Network was developed in collaboration with an expert specialist who regularly utilizes a non-automated diagnostic algorithm in clinical practice. The original Bayesian network was later refined using a more connected approach. Diagnoses determined from all automated approaches were compared with the diagnoses of a single human expert. In most cases, Bayesian networks were found to be at least as accurate as the Decision Tree approach. The refined Connected Bayesian Network was found to be more accurate than the Original Bayesian Network accurately discriminated between diagnoses despite the small sample size. In contrast, the Connected and Decision Tree approaches were less able to discriminate between diagnoses. The Original Bayesian Network was found to provide an excellent basis for graphically communicating the correlation between symptoms and laxity defects in a given anatomical zone. Performance measures in both networks indicate that Bayesian networks could provide a potentially useful tool in the management of female pelvic floor dysfunction. Before the technique can be utilized in practice, well-established learning algorithms should be applied to improve network structure. A larger training data set should also improve network accuracy, sensitivity, and specificity.

A comparative analysis of decision trees vis-à-vis other computational data mining techniques in automotive insurance fraud detection

The development and application of computational data mining techniques in financial fraud detection and business failure prediction has become a popular cross-disciplinary research area in recent times involving financial economists, forensic accountants and computational modellers. Some of the computational techniques popularly used in the context of - financial fraud detection and business failure prediction can also be effectively applied in the detection of fraudulent insurance claims and therefore, can be of immense practical value to the insurance industry. We provide a comparative analysis of prediction performance of a battery of data mining techniques using real-life automotive insurance fraud data. While the data we have used in our paper is US-based, the computational techniques we have tested can be adapted and generally applied to detect similar insurance frauds in other countries as well where an organized automotive insurance industry exists.