On the forced matching numbers of bipartite graphs

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matching of G. This notion has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Q(n), it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Q(n). Also we show an application to critical sets in back circulant Latin rectangles. (C) 2003 Elsevier B.V. All rights reserved.

Patient matching in treatment for alcohol dependence: is the null hypothesis still alive and well?

In the light of Project MATCH, is it reasonable to accept the null hypothesis that there are no clinically signi® cant matching effects between patient characteristics and cognitive± behaviour therapy (CBT), motivational enhancement therapy (MET) and Twelve-Step facilitation therapy (TSF)? The Project MATCH investigators considered the null hypothesis but preferred the alternative hypothesis that further analysis may reveal combinations of patient and therapist characteristics that show more substantial matching effects than any of the variables that they have examined to date.1

Applying machine learning to catalogue matching in astrophysics

We present the results of applying automated machine learning techniques to the problem of matching different object catalogues in astrophysics. In this study, we take two partially matched catalogues where one of the two catalogues has a large positional uncertainty. The two catalogues we used here were taken from the H I Parkes All Sky Survey (HIPASS) and SuperCOSMOS optical survey. Previous work had matched 44 per cent (1887 objects) of HIPASS to the SuperCOSMOS catalogue. A supervised learning algorithm was then applied to construct a model of the matched portion of our catalogue. Validation of the model shows that we achieved a good classification performance (99.12 per cent correct). Applying this model to the unmatched portion of the catalogue found 1209 new matches. This increases the catalogue size from 1887 matched objects to 3096. The combination of these procedures yields a catalogue that is 72 per cent matched.

Imitating the neighbours: vocal dialect matching in a mimic-model system

Vocal mimicry provides a unique system for investigating song learning and cultural evolution in birds. Male lyrebirds produce complex vocal displays that include extensive and accurate mimicry of many other bird species. We recorded and analysed the songs of the Albert's lyrebird (Menura alberti) and its most commonly imitated model species, the satin bowerbird (Ptilonorhynchus violaceus), at six sites in southeast Queensland, Australia. We show that each population of lyrebirds faithfully reproduces the song of the local population of bowerbirds. Within a population, lyrebirds show less variation in song structure than the available variation in the songs of the models. These results provide the first quantitative evidence for dialect matching in the songs of two species that have no direct ecological relationship.

Quantum-gate characterization in an extended Hilbert space

We describe an approach for characterizing the process performed by a quantum gate using quantum process tomography, by first modeling the gate in an extended Hilbert space, which includes nonqubit degrees of freedom. To prevent unphysical processes from being predicted, present quantum process tomography procedures incorporate mathematical constraints, which make no assumptions as to the actual physical nature of the system being described. By contrast, the procedure presented here assumes a particular class of physical processes, and enforces physicality by fitting the data to this model. This allows quantum process tomography to be performed using a smaller experimental data set, and produces parameters with a direct physical interpretation. The approach is demonstrated by example of mode matching in an all-optical controlled-NOT gate. The techniques described are general and could be applied to other optical circuits or quantum computing architectures.

3D protein structure matching by patch signatures

For determining functionality dependencies between two proteins, both represented as 3D structures, it is an essential condition that they have one or more matching structural regions called patches. As 3D structures for proteins are large, complex and constantly evolving, it is computationally expensive and very time-consuming to identify possible locations and sizes of patches for a given protein against a large protein database. In this paper, we address a vector space based representation for protein structures, where a patch is formed by the vectors within the region. Based on our previews work, a compact representation of the patch named patch signature is applied here. A similarity measure of two patches is then derived based on their signatures. To achieve fast patch matching in large protein databases, a match-and-expand strategy is proposed. Given a query patch, a set of small k-sized matching patches, called candidate patches, is generated in match stage. The candidate patches are further filtered by enlarging k in expand stage. Our extensive experimental results demonstrate encouraging performances with respect to this biologically critical but previously computationally prohibitive problem.

Crystallographic study of grain refinement in aluminum alloys using the edge-to-edge matching model

The edge-to-edge matching model for describing the interfacial crystallographic characteristics between two phases that are related by reproducible orientation relationships has been applied to the typical grain refiners in aluminum alloys. Excellent atomic matching between Al3Ti nucleating substrates, known to be effective nucleation sites for primary Al, and the Al matrix in both close packed directions and close packed planes containing these directions have been identified. The crystallographic features of the grain refiner and the Al matrix are very consistent with the edge-to-edge matching model. For three other typical grain refiners for Al alloys, TiC (when a = 0.4328 nm), TiB2 and AIB(2), the matching only occurs between the close packed directions in both phases and between the second close packed plane of the Al matrix and the second close packed plane of the refiners. According to the model, it is predicted that Al3Ti is a more powerful nucleating substrate for Al alloy than TiC, TiB2 and AlB2. This agrees with the previous experimental results. The present work shows that the edge-to-edge matching model has the potential to be a powerful tool in discovering new and more powerful grain refiners for Al alloys. (C) 2004 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.

Matching conditional moments in PDF modelling of nonpremixed combustion

The rate of generation of fluctuations with respect to the scalar values conditioned on the mixture fraction, which significantly affects turbulent nonpremixed combustion processes, is examined. Simulation of the rate in a major mixing model is investigated and the derived equations can assist in selecting the model parameters so that the level of conditional fluctuations is better reproduced by the models. A more general formulation of the multiple mapping conditioning (MMC) model that distinguishes the reference and conditioning variables is suggested. This formulation can be viewed as a methodology of enforcing certain desired conditional properties onto conventional mixing models. Examples of constructing consistent MMC models with dissipation and velocity conditioning as well as of combining MMC with large eddy simulations (LES) are also provided. (c) 2005 The Combustion Institute. Published by Elsevier Inc. All rights reserved.

Application of edge-to-edge matching model to understand the in-plane texture of TiSi2 (C49) thin films on (001)(Si) surface

The edge-to-edge matching model, which was originally developed for predicting crystallographic features in diffusional phase transformations in solids, has been used to understand the formation of in-plane textures in TiSi2 (C49) thin films on Si single crystal (001)si surface. The model predicts all the four previously reported orientation relationships between C49 and Si substrate based on the actual atom matching across the interface and the basic crystallographic data only. The model has strong potential to be used to develop new thin film materials. (c) 2006 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.

Understanding the crystallography of the eutectoid microstructure in a Zn-Al alloy using the edge-to-edge matching model

The orientation relationship (OR) between the beta(Zn) phase and the alpha(Al) phase and the corresponding habit planes in a Zn-Al eutectoid alloy were accurately determined using convergent beam Kikuchi line diffraction patterns. In addition to the previously reported OR. [11 (2) over bar0](beta)parallel to[110](alpha), (0002)(beta)parallel to ((1) over bar 11)alpha, two new ORs were observed. They are: [11 (2) over bar0](beta)parallel to [110], ((1) over bar 101)(beta) 0.82 degrees from (002)(alpha) and [(1) over bar 100](beta)parallel to[112](alpha), (0002)(beta) 4.5 degrees from (111)(alpha). These ORs can be explained and understood using the recently developed edge-to-edge matching model. (c) 2006 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.