314 research outputs found
Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs
No full textA connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c-1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs.
A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w₁,…,w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T₁,…, T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least (w_i)/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least (w_i)/3 and at most max({r,3}) w_i, where r ≥ 1 is the ratio between the largest and smallest value in w₁, … , w_k. In particular for the balanced version, i.e. w₁ = w₂ = , … , = w_k, this gives a partition with 1/3w_i ≤ w(T_i) ≤ 3w_i
Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix
No full textInternational audienceConsider a matrix of univariatepolynomials over a field . We study the problem of computing thecolumn rank profile of . To this end we first give an algorithmwhich improves the minimal kernel basis algorithm of Zhou, Labahn, andStorjohann (Proceedings ISSAC 2012). We then provide a second algorithm whichcomputes the column rank profile of with a rank-sensitivecomplexity of operations in .Here, is the sum of row degrees of , is the exponent ofmatrix multiplication, and hides logarithmic factors
Pepper-pot emittance measurement of laser-plasma wakefield accelerated electrons
No full textThe transverse emittance is an important parameter governing the brightness of an electron beam. Here we present the first pepper-pot measurement of the transverse emittance for a mono-energetic electron beam from a laser-plasma wakefield accelerator, carried out on the Advanced Laser-Plasma High Energy Accelerators towards X-Rays (ALPHA-X) beam line. Mono-energetic electrons are passed through an array of 52 mu m diameter holes in a tungsten mask. The pepper-pot results set an upper limit for the normalised emittance at 5.5 +/- 1 pi mm mrad for an 82 MeV beam
Angry sea wreaks vengeance on its destructors:fishing village pays for sins of coral miners
No full textBiliary Strictures Are Associated with Both Early and Late Hepatic Artery Stenosis
No full textBackground. Hepatic artery stenosis (HAS) following liver transplantation results in hypoperfusion and ischemic damage to the biliary tree. This study aimed to investigate how vascular intervention, liver function test derangement, and time point of HAS onset influence biliary complications. Methods. A single-center retrospective study of adult patients that underwent primary liver transplantation. Patients were grouped according to the presence or absence of HAS and then into early (≤90 d) or late (>90 d) subgroups. Biliary complications comprised anastomotic (AS) or non ASs (NASs). Results. Computed tomography angiography confirmed HAS was present in 39 of 1232 patients (3.2%). This occurred at ≤90 and >90 days in 20 (1.6%) and 19 (1.5%), respectively. The incidence of biliary strictures (BSs) in the group with HAS was higher than the group without (13/39; 33% versus 85/1193; 7.1%, P = 0.01). BS occurred in 8/20 (40.0%) and 5/19 (26.3%) of the early and late groups, respectively. The need for biliary intervention increased if any liver function test result was ≥3× upper limit of normal (P = 0.019). Conclusions. BS occurs at a significantly higher rate in the presence of HAS. Onset of HAS at ≤90 or ≥90 days can both be associated with morbidity. Significant liver function test derangement at HAS diagnosis indicates a higher likelihood of biliary intervention for strictures
Sensitivity analysis of wing aeroelastic responses
No full textDesign for prevention of aeroelastic instability (that is, the critical speeds leading to aeroelastic instability lie outside the operating range) is an integral part of the wing design process. Availability of the sensitivity derivatives of the various critical speeds with respect to shape parameters of the wing could be very useful to a designer in the initial design phase, when several design changes are made and the shape of the final configuration is not yet frozen. These derivatives are also indispensable for a gradient-based optimization with aeroelastic constraints.
In this study, flutter characteristic of a typical section in subsonic compressible flow is examined using a state-space unsteady aerodynamic representation. The sensitivity of the flutter speed of the typical section with respect to its mass and stiffness parameters, namely, mass ratio, static unbalance, radius of gyration, bending frequency and torsional frequency is calculated analytically. A strip-theory formulation is newly developed to represent the unsteady aerodynamic forces on a wing. This is coupled with an equivalent plate structural model based on a Rayleigh-Ritz formulation and the aeroelastic equations are solved as an eigenvalue problem to determine the critical speed of the wing. The sensitivity of divergence and flutter speeds to shape parameters, namely, aspect ratio, area, taper ratio and sweep angle are computed analytically. The aeroelastic equations are also integrated with respect to time using the Wilson-θ method at different values of freest ream speed, to observe the aeroelastic phenomena in real time. of divergence and flutter speeds to shape parameters, namely, aspect ratio, area, taper ratio and sweep angle are computed analytically. The aeroelastic equations are also integrated with respect to time using the Wilson-B method at different values of freest ream speed, to observe the aeroelastic phenomena in real time.
Flutter analysis of the wing is also carried out using a lifting-surface subsonic kernel function aerodynamic theory (FAST) and an equivalent plate structural model The flutter speed is obtained using a V-g type of solution. The novel method of automatic differentiation using ADIFOR is implemented to generate exact derivatives of the flutter speed with respect to shape and modal parameters of the wing.
Finite element modeling of the wing is done using NASTRAN so that wing structures made of spars and ribs and top and bottom wing skins could be analyzed. The free vibration modes of the wing obtained from NASTRAN are input into FAST to compute the flutter speed. The derivatives of flutter speed with respect to shape parameters are computed using a combination of central difference scheme and ADIFOR and the sensitivity to modal parameters is calculated using ADIFOR.
An equivalent plate model which incorporates first-order shear deformation theory is then examined so it can be used to model thick wings, where shear deformations are important. The sensitivity of natural frequencies to changes in shape parameters is obtained using ADIFOR. A simple optimization effort is made towards obtaining a minimum weight design of the wing, subject to flutter constraints, lift requirement constraints for level flight and side constraints on the planform parameters of the wing using the IMSL subroutine NCONG, which uses successive quadratic programming.Ph. D
Minimum energy force distribution for a walking robot
No full textHere, the foot force distribution for a six-legged walking machine is resolved for minimum energy consumption over a full cycle for regular wave gaits. Some insects utilize horizontal foot forces to reduce muscle forces and energy consumption [R. J. Full, R. Blickhan, and L. H. Ting, J. Exp. Biology 158 (1991), 369-390]. Foot force distribution for minimum energy consumption when applied to the walking machine, also supports this observation. In this study, geometric work loss for a walking machine with articulated legs is minimized by controlling interaction forces at the foot-ground interface. Minimum energy foot forces are studied for various duty factors, lateral offsets, link proportions, and friction between foot and ground. (C) 2001 , Inc
Scattering cross-sections of common calibration gases measured by IBBCEAS technique
No full textAbstractIn this study, incoherent broadband cavity-enhanced absorption spectroscopy (IBBCEAS) was used to measure scattering cross-sections of a few common gases in the 650–670nm spectral range relative to that of dry air. Precise measurements of scattering cross-sections of these calibration gases in the visible spectral range are important. The IBBCEAS system developed in the laboratory was calibrated with a low-loss optical window. The measurements made at 660nm were compared with previously measured cross-section values and found to be in good agreement with the existing measurements
Applications of real number theorem proving in PVS
No full textThis work is supported by funding from the EPSRC under grants EP/H500162, EP/F02309X and GR/S31242Real number theorem proving has many uses, particularly for verification of safety critical systems and systems for which design errors may be costly. We discuss a chain of developments building on real number theorem proving in PVS. This leads from the verification of aspects of an air traffic control system, through work on the integration of computer algebra and automated theorem proving to a new tool, NRV, first presented here that builds on the capabilities of Maple and PVS to provide a verified and automatic analysis of Nichols plots. This automates a standard technique used by control engineers and greatly improves assurance compared with the traditional method of visual inspection of the Nichols plots.Peer reviewe
Bright source of k alpha and continuum X rays by heating Kr clusters using a femtosecond laser
No full textX rays emitted from Kr clusters illuminated by a femtosecond laser have been observed over a wide spectral region from 3 keV to 15 keV. The measured spectra are characterized by a broad bremsstrahlung continuum and K[alpha], [beta] lines at 12.66 keV and 14.1 keV. To the best of the authors' knowledge, this is the first observation of K[alpha], [beta] emission from laser-heated Kr clusters. The bremsstrahlung continuum arising from collisions in the plasma implies a population of hot electrons consistent with a temperature of several kiloelectron volts. The absolute X-ray yield in the 3-15 keV region is found to be of the order of 107 photons per laser pulse. The plasma temperature, estimated from the continuum part of the spectrum as a function of laser intensity and X-ray yield as a function of laser pulse duration, are studied
- …
