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.

Wireless GPS-based phase-locked synchronization system for outdoor environment.

Synchronization of data coming from different sources is of high importance in biomechanics to ensure reliable analyses. This synchronization can either be performed through hardware to obtain perfect matching of data, or post-processed digitally. Hardware synchronization can be achieved using trigger cables connecting different devices in many situations; however, this is often impractical, and sometimes impossible in outdoors situations. The aim of this paper is to describe a wireless system for outdoor use, allowing synchronization of different types of - potentially embedded and moving - devices. In this system, each synchronization device is composed of: (i) a GPS receiver (used as time reference), (ii) a radio transmitter, and (iii) a microcontroller. These components are used to provide synchronized trigger signals at the desired frequency to the measurement device connected. The synchronization devices communicate wirelessly, are very lightweight, battery-operated and thus very easy to set up. They are adaptable to every measurement device equipped with either trigger input or recording channel. The accuracy of the system was validated using an oscilloscope. The mean synchronization error was found to be 0.39 μs and pulses are generated with an accuracy of <2 μs. The system provides synchronization accuracy about two orders of magnitude better than commonly used post-processing methods, and does not suffer from any drift in trigger generation.

Betweenness Centrality in Some Classes of Graphs

There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

Decision-usefulness of ideal cost- and ideal value accounting for valuation and stewardship

This paper contrasts the decision-usefulness of prototype accounting regimes based on perfect accounting for value, i.e. ideal value accounting (IVA), and perfect matching of cost, i.e. ideal cost accounting (ICA). The regimes are analyzed in the context of a firm with overlapping capacity investments where projects earn excess returns and residual income is utilized as performance indicator. Provided that IVA and ICA systematically differ based on the criterion of unconditional conservatism, we assess their respective decision-usefulness for different valuation- and stewardship-scenarios. Assuming that addressees solely observe current accounting data of the firm, ICA provides information which is useful for valuation and stewardship without reservation whereas IVA entails problems under specific assumptions.

Direct activation of microcrystalline zeolites

In this work a direct activation route of zeolites is assessed. It consists of NH4-exchanging the as-synthesized solids before removing the organic template. Calcination afterwards serves to combust the organic template and creates the Brønsted sites directly; thus applying merely a single thermal step. This method simplifies their activation and the material suffers less thermal stress. The approach was particularly effective for microcrystalline beta and ferrierite zeolites. Thorough investigation of the template content and materials' texture points out to three relevant effects that can explain the effective exchange process: partial removal of the template during exchange creates substantial microporosity (ferrierite), the remaining template is reorganized within the pores (ferrierite) and finally, void space can exist due to the non-perfect matching between the network and template (beta). This shorter method appears suited for microcrystalline zeolites; it was ineffective for crystalline MFI types. © 2013 Elsevier B.V. All rights reserved.

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

Performance Analysis of Topological Quantum Error Correcting Codes

In the last few years there has been a great development of techniques like quantum computers and quantum communication systems, due to their huge potentialities and the growing number of applications. However, physical qubits experience a lot of nonidealities, like measurement errors and decoherence, that generate failures in the quantum computation. This work shows how it is possible to exploit concepts from classical information in order to realize quantum error-correcting codes, adding some redundancy qubits. In particular, the threshold theorem states that it is possible to lower the percentage of failures in the decoding at will, if the physical error rate is below a given accuracy threshold. The focus will be on codes belonging to the family of the topological codes, like toric, planar and XZZX surface codes. Firstly, they will be compared from a theoretical point of view, in order to show their advantages and disadvantages. The algorithms behind the minimum perfect matching decoder, the most popular for such codes, will be presented. The last section will be dedicated to the analysis of the performances of these topological codes with different error channel models, showing interesting results. In particular, while the error correction capability of surface codes decreases in presence of biased errors, XZZX codes own some intrinsic symmetries that allow them to improve their performances if one kind of error occurs more frequently than the others.

Casimir interaction between a perfect conductor and graphene described by the Dirac model

We adopt the Dirac model for graphene and calculate the Casimir interaction energy between a plane suspended graphene sample and a parallel plane perfect conductor. This is done in two ways. First, we use the quantum-field-theory approach and evaluate the leading-order diagram in a theory with 2+1-dimensional fermions interacting with 3+1-dimensional photons. Next, we consider an effective theory for the electromagnetic field with matching conditions induced by quantum quasiparticles in graphene. The first approach turns out to be the leading order in the coupling constant of the second one. The Casimir interaction for this system appears to be rather weak. It exhibits a strong dependence on the mass of the quasiparticles in graphene.

Graphical models and point set matching

Point pattern matching in Euclidean Spaces is one of the fundamental problems in Pattern Recognition, having applications ranging from Computer Vision to Computational Chemistry. Whenever two complex patterns are encoded by two sets of points identifying their key features, their comparison can be seen as a point pattern matching problem. This work proposes a single approach to both exact and inexact point set matching in Euclidean Spaces of arbitrary dimension. In the case of exact matching, it is assured to find an optimal solution. For inexact matching (when noise is involved), experimental results confirm the validity of the approach. We start by regarding point pattern matching as a weighted graph matching problem. We then formulate the weighted graph matching problem as one of Bayesian inference in a probabilistic graphical model. By exploiting the existence of fundamental constraints in patterns embedded in Euclidean Spaces, we prove that for exact point set matching a simple graphical model is equivalent to the full model. It is possible to show that exact probabilistic inference in this simple model has polynomial time complexity with respect to the number of elements in the patterns to be matched. This gives rise to a technique that for exact matching provably finds a global optimum in polynomial time for any dimensionality of the underlying Euclidean Space. Computational experiments comparing this technique with well-known probabilistic relaxation labeling show significant performance improvement for inexact matching. The proposed approach is significantly more robust under augmentation of the sizes of the involved patterns. In the absence of noise, the results are always perfect.

Análises do matching de identidade generalizado por contingências de três e quatro termos: implicações para equivalência de estímulos

A expansão da tríplice continência em unidades com quatro ou mais elementos abriu novas perspectivas para a compreensão de comportamentos complexos, como a emergência de respostas que derivam da formação de classes de estímulos equivalentes e que modelam comportamentos simbólicos e conceituais. Na investigação experimental, o procedimento de matching to sample tem sido frequentemente empregado para estabelecer discriminações condicionais. Em particular, a obtenção do matching de identidade generalizado é considerada demonstrativa da aquisição dos conceitos de igualdade e diferença. Segundo argumentamos, o fato de se buscar a compreensão desses conceitos a partir de processos discriminativos condicionais pode ter sido responsável pelos frequentes fracassos em demonstrá-los em sujeitos não humanos. A falta de correspondência entre os processos discriminativos responsáveis por estabelecer a relação de reflexividade entre estímulos que formam classes equivalentes e o matching de identidade generalizado, nesse sentido, é aqui revista ao longo de estudos empíricos e discutida com respeito às suas implicações.

Intermediate motions and dipolar couplings as studied by Lee-Goldburg cross-polarization NMR: Hartmann-Hahn matching profiles

In this article, we evaluate the use of simple Lee-Goldburg cross-polarization (LG-CP) NMR experiments for obtaining quantitative information of molecular motion in the intermediate regime. In particular, we introduce the measurement of Hartmann-Hahn matching profiles for the assessment of heteronuclear dipolar couplings as well as dynamics as a reliable and robust alternative to the more common analysis of build-up curves. We have carried out dynamic spin dynamics simulations in order to test the method's sensitivity to intermediate motion and address its limitations concerning possible experimental imperfections. We further demonstrate the successful use of simple theoretical concepts, most prominently Anderson-Weiss (AW) theory, to analyze the data. We further propose an alternative way to estimate activation energies of molecular motions, based upon the acquisition of only two LG-CP spectra per temperature at different temperatures. As experimental tests, molecular jumps in imidazole methyl sulfonate, trimethylsulfoxonium iodide, and bisphenol A polycarbonate were investigated with the new method.

Ciratefi: An RST-invariant template matching with extension to color images

Template matching is a technique widely used for finding patterns in digital images. A good template matching should be able to detect template instances that have undergone geometric transformations. In this paper, we proposed a grayscale template matching algorithm named Ciratefi, invariant to rotation, scale, translation, brightness and contrast and its extension to color images. We introduce CSSIM (color structural similarity) for comparing the similarity of two color image patches and use it in our algorithm. We also describe a scheme to determine automatically the appropriate parameters of our algorithm and use pyramidal structure to improve the scale invariance. We conducted several experiments to compare grayscale and color Ciratefis with SIFT, C-color-SIFT and EasyMatch algorithms in many different situations. The results attest that grayscale and color Ciratefis are more accurate than the compared algorithms and that color-Ciratefi outperforms grayscale Ciratefi most of the time. However, Ciratefi is slower than the other algorithms.

Rotation-discriminating template matching based on Fourier coefficients of radial projections with robustness to scaling and partial occlusion

We consider brightness/contrast-invariant and rotation-discriminating template matching that searches an image to analyze A for a query image Q We propose to use the complex coefficients of the discrete Fourier transform of the radial projections to compute new rotation-invariant local features. These coefficients can be efficiently obtained via FFT. We classify templates in ""stable"" and ""unstable"" ones and argue that any local feature-based template matching may fail to find unstable templates. We extract several stable sub-templates of Q and find them in A by comparing the features. The matchings of the sub-templates are combined using the Hough transform. As the features of A are computed only once, the algorithm can find quickly many different sub-templates in A, and it is Suitable for finding many query images in A, multi-scale searching and partial occlusion-robust template matching. (C) 2009 Elsevier Ltd. All rights reserved.

The potential for increasing rubber production by matching tapping intensity to leaf area index

Understanding resource capture can help design appropriate species combinations, planting designs and management. Leaf area index (LAI) and its longevity are the most important factors defining dry matter production and thus growth and productivity. The ecophysiological modifications and yield of rubber (Hevea spp.) in an agroforestry system (AFS) with beans (Phaseolus vulgaris L.) were studied. The experiment was established in Southeast-Brazil, with three rubber cultivars: IAN 3087, RRIM 600 and RRIM 527. The AFS comprised double rows of rubber trees along with beans sown in autumn and winter seasons in 1999. There was about 50% higher rubber yield per tree in the AFS than the rubber monoculture. Trees within the AFS responded to higher solar radiation availability with higher LAI and total foliage area, allowing its greater interception. All three cultivars had higher LAI in the AFS than monoculture, reaching maximum values in the AFS between April and May of 3.17 for RRIM 527; 2.83 for RRIM 600 and 2.28 for IAN 3087. The maximum LAI values for monocrop rubber trees were: 2.65, 2.62 and 1.99, respectively, for each cultivar. Rubber production and LAI were positively correlated in both the AFS and monoculture but leaf fall of rubber trees in the AFS was delayed and total phytomass was larger. It is suggested that trees in the AFS were under exploited and could yield more without compromising their life cycle if the tapping system was intensified. This shows how knowledge of LAI can be used to manage tapping intensity in the field, leading to higher rubber yield.

A matching pursuit-based signal complexity measure for the analysis of newborn EEG

This paper presents a new relative measure of signal complexity, referred to here as relative structural complexity, which is based on the matching pursuit (MP) decomposition. By relative, we refer to the fact that this new measure is highly dependent on the decomposition dictionary used by MP. The structural part of the definition points to the fact that this new measure is related to the structure, or composition, of the signal under analysis. After a formal definition, the proposed relative structural complexity measure is used in the analysis of newborn EEG. To do this, firstly, a time-frequency (TF) decomposition dictionary is specifically designed to compactly represent the newborn EEG seizure state using MP. We then show, through the analysis of synthetic and real newborn EEG data, that the relative structural complexity measure can indicate changes in EEG structure as it transitions between the two EEG states; namely seizure and background (non-seizure).