On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

Density profiles in the raise and peel model with and without a wall; physics and combinatorics

We consider the raise and peel model of a one-dimensional fluctuating interface in the presence of an attractive wall. The model can also describe a pair annihilation process in disordered unquenched media with a source at one end of the system. For the stationary states, several density profiles are studied using Monte Carlo simulations. We point out a deep connection between some profiles seen in the presence of the wall and in its absence. Our results are discussed in the context of conformal invariance ( c = 0 theory). We discover some unexpected values for the critical exponents, which are obtained using combinatorial methods. We have solved known ( Pascal`s hexagon) and new (split-hexagon) bilinear recurrence relations. The solutions of these equations are interesting in their own right since they give information on certain classes of alternating sign matrices.

On the asymptotic enumeration of accessible automata

We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.

Classification of normal swallowing and oropharyngeal dysphagia using wavelet

Oropharyngeal dysphagia is characterized by any alteration in swallowing dynamics which may lead to malnutrition and aspiration pneumonia. Early diagnosis is crucial for the prognosis of patients with dysphagia, and the best method for swallowing dynamics assessment is swallowing videofluoroscopy, an exam performed with X-rays. Because it exposes patients to radiation, videofluoroscopy should not be performed frequently nor should it be prolonged. This study presents a non-invasive method for the pre-diagnosis of dysphagia based on the analysis of the swallowing acoustics, where the discrete wavelet transform plays an important role to increase sensitivity and specificity in the identification of dysphagic patients. (C) 2008 Elsevier Inc. All rights reserved.

Wavelet-Galerkin method for one-dimensional elastoplasticity and damage problems: Constitutive modeling and computational aspects

This work presents an analysis of the wavelet-Galerkin method for one-dimensional elastoplastic-damage problems. Time-stepping algorithm for non-linear dynamics is presented. Numerical treatment of the constitutive models is developed by the use of return-mapping algorithm. For spacial discretization we can use wavelet-Galerkin method instead of standard finite element method. This approach allows to locate singularities. The discrete formulation developed can be applied to the simulation of one-dimensional problems for elastic-plastic-damage models. (C) 2007 Elsevier Inc. All rights reserved.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Singular Perturbation for the Discounted Continuous Control of Piecewise Deterministic Markov Processes

This paper deals with the expected discounted continuous control of piecewise deterministic Markov processes (PDMP`s) using a singular perturbation approach for dealing with rapidly oscillating parameters. The state space of the PDMP is written as the product of a finite set and a subset of the Euclidean space a""e (n) . The discrete part of the state, called the regime, characterizes the mode of operation of the physical system under consideration, and is supposed to have a fast (associated to a small parameter epsilon > 0) and a slow behavior. By using a similar approach as developed in Yin and Zhang (Continuous-Time Markov Chains and Applications: A Singular Perturbation Approach, Applications of Mathematics, vol. 37, Springer, New York, 1998, Chaps. 1 and 3) the idea in this paper is to reduce the number of regimes by considering an averaged model in which the regimes within the same class are aggregated through the quasi-stationary distribution so that the different states in this class are replaced by a single one. The main goal is to show that the value function of the control problem for the system driven by the perturbed Markov chain converges to the value function of this limit control problem as epsilon goes to zero. This convergence is obtained by, roughly speaking, showing that the infimum and supremum limits of the value functions satisfy two optimality inequalities as epsilon goes to zero. This enables us to show the result by invoking a uniqueness argument, without needing any kind of Lipschitz continuity condition.

Reduced gradient method combined with augmented Lagrangian and barrier for the optimal power flow problem

A new approach for solving the optimal power flow (OPF) problem is established by combining the reduced gradient method and the augmented Lagrangian method with barriers and exploring specific characteristics of the relations between the variables of the OPF problem. Computer simulations on IEEE 14-bus and IEEE 30-bus test systems illustrate the method. (c) 2007 Elsevier Inc. All rights reserved.

An evaluation of three upwinding approximations for numerical modeling the flow in tubular membrane of Newtonian and non-Newtonian fluids

In this paper, the laminar fluid flow of Newtonian and non-Newtonian of aqueous solutions in a tubular membrane is numerically studied. The mathematical formulation, with associated initial and boundary conditions for cylindrical coordinates, comprises the mass conservation, momentum conservation and mass transfer equations. These equations are discretized by using the finite-difference technique on a staggered grid system. Comparisons of the three upwinding schemes for discretization of the non-linear (convective) terms are presented. The effects of several physical parameters on the concentration profile are investigated. The numerical results compare favorably with experimental data and the analytical solutions. (C) 2011 Elsevier Inc. All rights reserved.

Investigating relationships within and between category networks in Wikipedia

This work maps and analyses cross-citations in the areas of Biology, Mathematics, Physics and Medicine in the English version of Wikipedia, which are represented as an undirected complex network where the entries correspond to nodes and the citations among the entries are mapped as edges. We found a high value of clustering coefficient for the areas of Biology and Medicine, and a small value for Mathematics and Physics. The topological organization is also different for each network, including a modular structure for Biology and Medicine, a sparse structure for Mathematics and a dense core for Physics. The networks have degree distributions that can be approximated by a power-law with a cut-off. The assortativity of the isolated networks has also been investigated and the results indicate distinct patterns for each subject. We estimated the betweenness centrality of each node considering the full Wikipedia network, which contains the nodes of the four subjects and the edges between them. In addition, the average shortest path length between the subjects revealed a close relationship between the subjects of Biology and Physics, and also between Medicine and Physics. Our results indicate that the analysis of the full Wikipedia network cannot predict the behavior of the isolated categories since their properties can be very different from those observed in the full network. (C) 2011 Elsevier Ltd. All rights reserved.

Relative entropy measures applied to healthy and pathological voice characterization

Nowadays, noninvasive methods of diagnosis have increased due to demands of the population that requires fast, simple and painless exams. These methods have become possible because of the growth of technology that provides the necessary means of collecting and processing signals. New methods of analysis have been developed to understand the complexity of voice signals, such as nonlinear dynamics aiming at the exploration of voice signals dynamic nature. The purpose of this paper is to characterize healthy and pathological voice signals with the aid of relative entropy measures. Phase space reconstruction technique is also used as a way to select interesting regions of the signals. Three groups of samples were used, one from healthy individuals and the other two from people with nodule in the vocal fold and Reinke`s edema. All of them are recordings of sustained vowel /a/ from Brazilian Portuguese. The paper shows that nonlinear dynamical methods seem to be a suitable technique for voice signal analysis, due to the chaotic component of the human voice. Relative entropy is well suited due to its sensibility to uncertainties, since the pathologies are characterized by an increase in the signal complexity and unpredictability. The results showed that the pathological groups had higher entropy values in accordance with other vocal acoustic parameters presented. This suggests that these techniques may improve and complement the recent voice analysis methods available for clinicians. (C) 2008 Elsevier Inc. All rights reserved.

Billiards in a General Domain with Random Reflections

We study stochastic billiards on general tables: a particle moves according to its constant velocity inside some domain D R(d) until it hits the boundary and bounces randomly inside, according to some reflection law. We assume that the boundary of the domain is locally Lipschitz and almost everywhere continuously differentiable. The angle of the outgoing velocity with the inner normal vector has a specified, absolutely continuous density. We construct the discrete time and the continuous time processes recording the sequence of hitting points on the boundary and the pair location/velocity. We mainly focus on the case of bounded domains. Then, we prove exponential ergodicity of these two Markov processes, we study their invariant distribution and their normal (Gaussian) fluctuations. Of particular interest is the case of the cosine reflection law: the stationary distributions for the two processes are uniform in this case, the discrete time chain is reversible though the continuous time process is quasi-reversible. Also in this case, we give a natural construction of a chord ""picked at random"" in D, and we study the angle of intersection of the process with a (d - 1) -dimensional manifold contained in D.

SPECIAL CHARACTERIZATIONS OF STANDARD DISCRETE MODELS

This article presents important properties of standard discrete distributions and its conjugate densities. The Bernoulli and Poisson processes are described as generators of such discrete models. A characterization of distributions by mixtures is also introduced. This article adopts a novel singular notation and representation. Singular representations are unusual in statistical texts. Nevertheless, the singular notation makes it simpler to extend and generalize theoretical results and greatly facilitates numerical and computational implementation.

Histopathological evaluation of root canal filling materials for primary teeth

This study aimed to assess the response of apical and periapical tissues of dogs' teeth after root canal filling with different materials. Forty roots from dogs' premolars were prepared biomechanically and assigned to 4 groups filled with: Group I: commercial calcium hydroxide and polyethylene glycol-based paste (Calen®) thickened with zinc oxide; Group II: paste composed of iodoform, Rifocort® and camphorated paramonochlorophenol; Group III: zinc oxide-eugenol cement; Group IV: sterile saline. After 30 days, the samples were subjected to histological processing. The histopathological findings revealed that in Groups I and IV the apical and periapical regions exhibited normal appearance, with large number of fibers and cells and no resorption of mineralized tissues. In Group II, mild inflammatory infiltrate and mild edema were observed, with discrete fibrogenesis and bone resorption. Group III showed altered periapical region and thickened periodontal ligament with presence of inflammatory cells and edema. It may be concluded that the Calen paste thickened with zinc oxide yielded the best tissue response, being the most indicated material for root canal filling of primary teeth with pulp vitality.

Subcutaneous tissue response of isogenic mice to calcium hydroxide-based pastes with chlorhexidine

This study was evaluated the response of subcutaneous connective tissue of isogenic mice to calcium hydroxide-based pastes with chlorhexidine digluconate (CHX). Seventy isogenic male BALB/c mice aged 6-8 weeks and weighing 15-20 g were randomly assigned to 8 groups. The animals received polyethylene tube implants as follows: Groups I, II, and III (n=10) - Calen® paste mixed with 0.4% CHX (experimental paste; Calen/CHX) for 7, 21, and 63 days, respectively; Groups IV, V, and VI (n=10) - UltraCal™ paste mixed with 2% CHX (experimental paste supplied by Ultradent Products Inc.; Ultracal/CHX) for 7, 21, and 63 days, respectively; and Groups VII and VIII (n=5): empty tube for 7 and 21 days, respectively. At the end of the experimental periods, the implants were removed together with the surrounding tissues (skin and subcutaneous connective tissue). The biopsied tissues were subjected to routine processing for histological analysis. Using a descriptive analysis and a four-point (0-3) scoring system, the following criteria were considered for qualitative and quantitative analysis of the tissue around the implanted materials: collagen fiber formation, tissue thickness and inflammatory infiltrate. A quantitative analysis was performed by measuring the thickness (µm), area (µm²) and perimeter (µm) of the reactionary granulomatous tissue formed at the tube ends. Data were analyzed statistically by the Kruskal-Wallis test and Dunn's post-test (α=0.05). Calen/CHX showed biocompatibility with the subcutaneous and reactionary tissues, with areas of discrete fibrosis and normal conjunctive fibrous tissue, though without statistically significant difference (p>0.05) from the control groups. In Groups I to III, there was a predominance of score 1, while in Groups IV to VI scores 2 and 3 predominated for all analyzed parameters. UltraCal/CHX, on the other hand, induced the formation of an inflammatory infiltrate and abundant exudate, suggesting a persistent residual aggression from the material, even 63 days after implant placement. In conclusion, the Calen paste mixed with 0.4% CHX allowed an adequate tissue response, whereas the UltraCal paste mixed with 2% CHX showed unsatisfactory results.