Hall conditions for edge-weighted bipartite graphs

A weighted variant of Hall's condition for the existence of matchings is shown to be equivalent to the existence of a matching in a lexicographic product. This is used to introduce characterizations of those bipartite graphs whose edges may be replicated so as to yield semiregular multigraphs or, equivalently, semiregular edge-weightings. Such bipartite graphs will be called semiregularizable. Some infinite families of semiregularizable trees are described and all semiregularizable trees on at most 11 vertices are listed. Matrix analogues of some of the results are mentioned and are shown to imply some of the known characterizations of regularizable graphs.

A weighted bilateral shift with cyclic square is supercyclic

It is shown, for a bounded weighted bilateral shift T acting on l(p)(Z), and for 1

Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.

Controls on the contemporary distribution of lake thecamoebians (testate amoebae) in the Greater Toronto Area and their potential as water quality indicators.

Thecamoebians were examined from 71 surface sediment samples collected from 21 lakes and ponds in the Greater Toronto Area to (1) elucidate the controls on faunal distribution in modern lake environments; and (2) to consider the utility of thecamoebians in quantitative studies of water quality change. This area was chosen because it includes a high density of kettle and other lakes which are threatened by urban development and where water quality has deteriorated locally as a result of contaminant inputs, particularly nutrients. Fifty-eight samples yielded statistically significant thecamoebian populations. The most diverse faunas (highest Shannon Diversity Index values) were recorded in lakes beyond the limits of urban development, although the faunas of all lakes showed signs of sub-optimal conditions. The assemblages were divided into five clusters using Q-mode cluster analysis, supported by Detrended Correspondence Analysis. Canonical Correspondence Analysis (CCA) was used to examine species-environment relationships and to explain the observed clusterings. Twenty-four measured environmental variables were considered, including water property attributes (e.g., pH, conductivity, dissolved oxygen), substrate characteristics, sediment-based phosphorus (Olsen P) and 11 environmentally available metals. The thecamoebian assemblages showed a strong association with phosphorus, reflecting the eutrophic status of many of the lakes, and locally to elevated conductivity measurements, which appear to reflect road salt inputs associated with winter de-icing operations. Substrate characteristics, total organic carbon and metal contaminants (particularly Cu and Mg) also influenced the faunas of some samples. A series of partial CCAs show that of the measured variables, sedimentary phosphorus has the largest influence on assemblage distribution, explaining 6.98% (P < 0.002) of the total variance. A transfer function was developed for sedimentary phosphorus (Olsen P) using 58 samples from 15 of the studied lakes. The best performing model was based on weighted averaging with inverse deshrinking (WA Inv, r jack 2= 0.33, RMSEP = 102.65 ppm). This model was applied to a small modern thecamoebian dataset from a eutrophic lake in northern Ontario to predict phosphorus and performed satisfactorily. This preliminary study confirms that thecamoebians have considerable potential as quantitative water quality indicators in urbanising regions, particularly in areas influenced by nutrient inputs and road salts.

The outflow ranking method for weighted directed graphs

A ranking method assigns to every weighted directed graph a (weak) ordering of the nodes. In this paper we axiomatize the ranking method that ranks the nodes according to their outflow using four independent axioms. Besides the well-known axioms of anonymity and positive responsiveness we introduce outflow monotonicity – meaning that in pairwise comparison between two nodes, a node is not doing worse in case its own outflow does not decrease and the other node’s outflow does not increase – and order preservation – meaning that adding two weighted digraphs such that the pairwise ranking between two nodes is the same in both weighted digraphs, then this is also their pairwise ranking in the ‘sum’ weighted digraph. The outflow ranking method generalizes the ranking by outdegree for directed graphs, and therefore also generalizes the ranking by Copeland score for tournaments.

Compact Toffoli gate using weighted graph states

We introduce three compact graph states that can be used to perform a measurement-based Toffoli gate. Given a weighted graph of six, seven, or eight qubits, we show that success probabilities of 1/4, 1/2, and 1, respectively, can be achieved. Our study puts a measurement-based version of this important quantum logic gate within the reach of current experiments. As the graphs are setup independent, they could be realized in a variety of systems, including linear optics and ion traps.

Increasing the accuracy of Nitrogen Dioxide (NO2) pollution mapping using geographically weighted regression (GWR) and geostatistics.

Nitrogen Dioxide (NO2) is known to act as an environmental trigger for many respiratory illnesses. As a pollutant it is difficult to map accurately, as concentrations can vary greatly over small distances. In this study three geostatistical techniques were compared, producing maps of NO2 concentrations in the United Kingdom (UK). The primary data source for each technique was NO2 point data, generated from background automatic monitoring and background diffusion tubes, which are analysed by different laboratories on behalf of local councils and authorities in the UK. The techniques used were simple kriging (SK), ordinary kriging (OK) and simple kriging with a locally varying mean (SKlm). SK and OK make use of the primary variable only. SKlm differs in that it utilises additional data to inform prediction, and hence potentially reduces uncertainty. The secondary data source was Oxides of Nitrogen (NOx) derived from dispersion modelling outputs, at 1km x 1km resolution for the UK. These data were used to define the locally varying mean in SKlm, using two regression approaches: (i) global regression (GR) and (ii) geographically weighted regression (GWR). Based upon summary statistics and cross-validation prediction errors, SKlm using GWR derived local means produced the most accurate predictions. Therefore, using GWR to inform SKlm was beneficial in this study.

Development of an Arcellacean (testate lobose amoebae) based transfer function for sedimentary phosphorous in lakes.

Arcellacea (testate lobose amoebae) communities were assessed from 73 sediment-water interface samples collected from 33 lakes in urban and rural settings within the Greater Toronto Area (GTA), Ontario, Canada, as well as from forested control areas in the Lake Simcoe area, Algonquin Park and eastern Ontario. The results were used to: (1) develop a statistically rigorous arcellacean-based training set for sedimentary phosphorus (Olsen P (OP)) loading; and (2) derive a transfer function to reconstruct OP levels during the post-European settlement era (AD1870s onward) using a chronologically well-constrained core from Haynes Lake on the environmentally sensitive Oak Ridges Moraine, within the GTA. Ordination analysis indicated that OP most influenced arcellacean assemblages, explaining 6.5% (p < 0.005) of total variance. An improved training set where the influence of other important environmental variables (e.g. total organic carbon, total nitrogen, Mg) was reduced, comprised 40 samples from 31 lakes, and was used to construct a transfer function for lacustrine arcellaceans for sedimentary phosphorus (Olsen P) using tolerance downweighted weighted averaging (WA-Tol) with inverse deshrinking (RMSEPjack-77pp; r2jack = 0.68). The inferred reconstruction indicates that OP levels remained near pre-settlement background levels from settlement in the late AD 1970s through to the early AD 1970s. Since OP runoff from both forests and pasture is minimal, early agricultural land use within the lake catchment was as most likely pasture and/or was used to grow perennial crops such as Timothy-grass for hay. A significant increase in inferred OP concentration beginning ~ AD 1972 may have been related to a change in crops (e.g. corn production) in the catchment resulting in more runoff, and the introduction of chemical fertilizers. A dramatic decline in OP after ~ AD 1985 probably corresponds to a reduction in chemical fertilizer use related to advances in agronomy, which permitted a more precise control over required fertilizer application. Another significant increase in OP levels after ~ AD 1995 may have been related to the construction of a large golf course upslope and immediately to the north of Haynes Lake in AD 1993, where significant fertilizer use is required to maintain the fairways. These results demonstrate that arcellaceans have great potential for reconstructing lake water geochemistry and will complement other proxies (e.g. diatoms) in paleolimnological research.

Optimization of Weighted Finite State Transducer for Speech Recognition

There is considerable interest in creating embedded, speech recognition hardware using the weighted finite state transducer (WFST) technique but there are performance and memory usage challenges. Two system optimization techniques are presented to address this; one approach improves token propagation by removing the WFST epsilon input arcs; another one-pass, adaptive pruning algorithm gives a dramatic reduction in active nodes to be computed. Results for memory and bandwidth are given for a 5,000 word vocabulary giving a better practical performance than conventional WFST; this is then exploited in an adaptive pruning algorithm that reduces the active nodes from 30,000 down to 4,000 with only a 2 percent sacrifice in speech recognition accuracy; these optimizations lead to a more simplified design with deterministic performance.