Maximum Series-Parallel Subgraph

Consider the NP-hard problem of, given a simple graph G, to find a series-parallel subgraph of G with the maximum number of edges. The algorithm that, given a connected graph G, outputs a spanning tree of G, is a 1/2-approximation. Indeed, if n is the number of vertices in G, any spanning tree in G has n-1 edges and any series-parallel graph on n vertices has at most 2n-3 edges. We present a 7/12 -approximation for this problem and results showing the limits of our approach.

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.

Metamorfose planar via métodos Level Set e Particle Level Set para a reconstrução de superfícies tridimensionais

Evolving interfaces were initially focused on solutions to scientific problems in Fluid Dynamics. With the advent of the more robust modeling provided by Level Set method, their original boundaries of applicability were extended. Specifically to the Geometric Modeling area, works published until then, relating Level Set to tridimensional surface reconstruction, centered themselves on reconstruction from a data cloud dispersed in space; the approach based on parallel planar slices transversal to the object to be reconstructed is still incipient. Based on this fact, the present work proposes to analyse the feasibility of Level Set to tridimensional reconstruction, offering a methodology that simultaneously integrates the proved efficient ideas already published about such approximation and the proposals to process the inherent limitations of the method not satisfactorily treated yet, in particular the excessive smoothing of fine characteristics of contours evolving under Level Set. In relation to this, the application of the variant Particle Level Set is suggested as a solution, for its intrinsic proved capability to preserve mass of dynamic fronts. At the end, synthetic and real data sets are used to evaluate the presented tridimensional surface reconstruction methodology qualitatively.

Metamorfose planar via métodos Level Set e Particle Level Set para a reconstrução de superfícies tridimensionais

Evolving interfaces were initially focused on solutions to scientific problems in Fluid Dynamics. With the advent of the more robust modeling provided by Level Set method, their original boundaries of applicability were extended. Specifically to the Geometric Modeling area, works published until then, relating Level Set to tridimensional surface reconstruction, centered themselves on reconstruction from a data cloud dispersed in space; the approach based on parallel planar slices transversal to the object to be reconstructed is still incipient. Based on this fact, the present work proposes to analyse the feasibility of Level Set to tridimensional reconstruction, offering a methodology that simultaneously integrates the proved efficient ideas already published about such approximation and the proposals to process the inherent limitations of the method not satisfactorily treated yet, in particular the excessive smoothing of fine characteristics of contours evolving under Level Set. In relation to this, the application of the variant Particle Level Set is suggested as a solution, for its intrinsic proved capability to preserve mass of dynamic fronts. At the end, synthetic and real data sets are used to evaluate the presented tridimensional surface reconstruction methodology qualitatively.

Angular-planar CMB power spectrum

Gaussianity and statistical isotropy of the Universe are modern cosmology's minimal set of hypotheses. In this work we introduce a new statistical test to detect observational deviations from this minimal set. By defining the temperature correlation function over the whole celestial sphere, we are able to independently quantify both angular and planar dependence (modulations) of the CMB temperature power spectrum over different slices of this sphere. Given that planar dependence leads to further modulations of the usual angular power spectrum C(l), this test can potentially reveal richer structures in the morphology of the primordial temperature field. We have also constructed an unbiased estimator for this angular-planar power spectrum which naturally generalizes the estimator for the usual C(l)'s. With the help of a chi-square analysis, we have used this estimator to search for observational deviations of statistical isotropy in WMAP's 5 year release data set (ILC5), where we found only slight anomalies on the angular scales l = 7 and l = 8. Since this angular-planar statistic is model-independent, it is ideal to employ in searches of statistical anisotropy (e.g., contaminations from the galactic plane) and to characterize non-Gaussianities.

Absorption of planar waves in a draining bathtub

We present an analysis of the absorption of acoustic waves by a black hole analogue in (2 + 1) dimensions generated by a fluid flow in a draining bathtub. We show that the low-frequency absorption length is equal to the acoustic hole circumference and that the high-frequency absorption length is 4 times the ergoregion radius. For intermediate values of the wave frequency, we compute the absorption length numerically and show that our results are in excellent agreement with the low-and high-frequency limits. We analyze the occurrence of superradiance, manifested as negative partial absorption lengths for corotating modes at low frequencies.

Numerical evidence against a conjecture on the cover time of planar graphs

We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time tau (G(N)) of a planar graph G(N) of N vertices and maximal degree d is lower bounded by tau (G(N)) >= C(d)N(lnN)(2) with C(d) = (d/4 pi) tan(pi/d), with equality holding for some geometries. We tested this conjecture on the regular honeycomb (d = 3), regular square (d = 4), regular elongated triangular (d = 5), and regular triangular (d = 6) lattices, as well as on the nonregular Union Jack lattice (d(min) = 4, d(max) = 8). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violate the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.

Calculating current densities and fields due to shielded bi-planar radio-frequency coils

A method for the accurate computation of the current densities produced in a wide-runged bi-planar radio-frequency coil is presented. The device has applications in magnetic resonance imaging. There is a set of opposing primary rungs, symmetrically placed on parallel planes and a similar arrangement of rungs on two parallel planes surrounding the primary serves as a shield. Current densities induced in these primary and shielding rungs are calculated to a high degree of accuracy using an integral-equation approach, combined with the inverse finite Hilbert transform. Once these densities are known, accurate electrical and magnetic fields are then computed without difficulty. Some test results are shown. The method is so rapid that it can be incorporated into optimization software. Some preliminary fields produced from optimized coils are presented.

Er(3+) doped phosphoniobate glasses and planar waveguides: structural and optical properties

Phosphoniobate glasses with composition (mol%) (100-x) NaPO(3)-xNb(2)O(5) ( x varying from 11 to 33) were prepared and characterized by means of thermal analysis, Fourier transform infrared spectroscopy, Raman scattering and (31)P nuclear magnetic resonance. The addition of Nb(2)O(5) to the polyphosphate base glass leads to depolymerization of the metaphosphate structure. Different colors were observed and assigned as indicating the presence of Nb(4+) ions, as confirmed by electron paramagnetic resonance measurements. The color was observed to depend on the glass composition and melting temperature as well. Er(3+) containing samples were also prepared. Strong emission in the 1550 nm region was observed. The Er(3+4)I(15/2) emission quantum efficiency was observed to be 90% and the quenching concentration was observed to be 1.1 mol%( 1.45 x 10(20) ions cm(-3)). Planar waveguides were prepared by Na(+)-K(+)-Ag(+) ion exchange with Er(3+) containing samples. Optical parameters of the waveguides were measured at 632.8, 543.5 and 1550 nm by the prism coupling technique as a function of the ion exchange time and Ag(+) concentration. The optimized planar waveguides show a diffusion depth of 5.9 mu m and one propagating mode at 1550 nm.

Erbium-activated silica-zirconia planar waveguides prepared by sol-gel route

Er(3+) doped (100-x)SiO(2)-xZrO(2) planar waveguides were prepared by the sol-gel route, with x ranging from 10 up to 30 mol%. Multilayer films doped with 0.3 mol% Er(3+) ions were deposited on fused quartz substrates by the dip-coating technique. The thickness and refractive index were measured by m-line spectroscopy at different wavelengths. The fabrication protocol was optimized in order to confine one propagating mode at 1.5 mu m. Photoluminescence in the near and visible region indicated a crystalline local environment for the Er(3+) ion. (c) 2007 Elsevier B.V. All rights reserved.

The design of planar gradient coils. Part I: A winding path correction method

In this work a new approach for designing planar gradient coils is outlined for the use in an existing MRI apparatus. A technique that allows for gradient field corrections inside the diameter-sensitive volume is deliberated. These corrections are brought about by making changes to the wire paths that constitute the coil windings, and hence, is called the path correction method. The existing well-known target held method is used to gauge the performance of a typical gradient coil. The gradient coil design methodology is demonstrated for planar openable gradient coils that can be inserted into an existing MRI apparatus. The path corrected gradient coil is compared to the coil obtained using the target field method. It is shown that using a wire path correction with optimized variables, winding patterns that can deliver high magnetic gradient field strengths and large imaging regions can be obtained.

Supersonic velocimetry in a shock tube using laser enhanced ionisation and planar laser induced fluorescence

A novel flow-tagging technique is presented which was employed to measure gas velocities in the free stream of a shock tube. This method is based on the laser spectroscopic techniques of Laser-Enhanced Ionisation (LEI) and Laser-Induced Fluorescence (LIF). The flow in the shock tube is seeded with small amounts of sodium, and LEI is used to produce a substantial depletion of neutral sodium atom concentration in a well-defined region of the flow, by using two wavelength-resonance excitation and subsequent collisional ionisation. At a specific time delay, single-laser-pulse planar LIF is utilised to produce a two-dimensional (2-D) inverse image of the depleted tagged region downstream of the flow. By measuring the displacement of the tagged region, free stream velocities in a shock tube were determined. Large variations in the concentration of sodium seeded into the flow were observed and even in the presence of these large variations accurate free-stream velocity measurements were obtained. The experimentally determined value for velocity compares very well with the predicted velocity.

Measurements of neutral atom diffusion and electron-ion recombination by laser enhanced ionisation and planar laser induced fluorescence in an air-acetylene flame

The spatial and temporal evolution of a depleted atomic distribution created by laser enhanced ionisation (LEI) was employed to determine both a diffusion coefficient for sodium (Na) and an electron (e(-)) and sodium ion recombination rate coefficient in an analytical air-C2H2 flame. A depleted distribution of neutral sodium atoms was produced in a flame by ionising approximately 80% of the irradiated sodium atoms in a well defined region using a two step LEI excitation scheme. Following depletion by ionisation, planar laser induced fluorescence (PLIF) images of the depleted region recorded the diffusion and decay of the depleted Na distribution for different depletion-probe delays. From measurements of the diffused width of the distribution, an accurate diffusion coefficient D = (1.19 +/- 0.03) x 10(-3) m(2) s(-1) for Na was determined in teh burnt gases of the flame. Measurements of the integrated fluorescence intensity in the depleted region for different depletion-probe delays were related to an increase in atomic sodium concentration caused by electron-ion recombination. At high concentrations (greater than or equal to 50 mu g ml(-1)), where the electron and ion concentrations in the depleted region were assumed equal, a recombination rate coefficient of 4.2 x 10(-9) cm(3) s(-1) was calculated. (C) 1997 Elsevier Science B.V.