Vertex splitting and connectivity augmentation in hypergraphs

We consider problems of splitting and connectivity augmentation in hypergraphs. In a hypergraph G = (V +s, E), to split two edges su, sv, is to replace them with a single edge uv. We are interested in doing this in such a way as to preserve a defined level of connectivity in V . The splitting technique is often used as a way of adding new edges into a graph or hypergraph, so as to augment the connectivity to some prescribed level. We begin by providing a short history of work done in this area. Then several preliminary results are given in a general form so that they may be used to tackle several problems. We then analyse the hypergraphs G = (V + s, E) for which there is no split preserving the local-edge-connectivity present in V. We provide two structural theorems, one of which implies a slight extension to Mader’s classical splitting theorem. We also provide a characterisation of the hypergraphs for which there is no such “good” split and a splitting result concerned with a specialisation of the local-connectivity function. We then use our splitting results to provide an upper bound on the smallest number of size-two edges we must add to any given hypergraph to ensure that in the resulting hypergraph we have λ(x, y) ≥ r(x, y) for all x, y in V, where r is an integer valued, symmetric requirement function on V*V. This is the so called “local-edge-connectivity augmentation problem” for hypergraphs. We also provide an extension to a Theorem of Szigeti, about augmenting to satisfy a requirement r, but using hyperedges. Next, in a result born of collaborative work with Zoltán Király from Budapest, we show that the local-connectivity augmentation problem is NP-complete for hypergraphs. Lastly we concern ourselves with an augmentation problem that includes a locational constraint. The premise is that we are given a hypergraph H = (V,E) with a bipartition P = {P1, P2} of V and asked to augment it with size-two edges, so that the result is k-edge-connected, and has no new edge contained in some P(i). We consider the splitting technique and describe the obstacles that prevent us forming “good” splits. From this we deduce results about which hypergraphs have a complete Pk-split. This leads to a minimax result on the optimal number of edges required and a polynomial algorithm to provide an optimal augmentation.

rho D*D* vertex from QCD sum rules

We calculate the form factors and the coupling constant in the rho D*D* vertex in the framework of QCD sum rules. We evaluate the three point correlation functions of the vertex considering both rho and D* mesons off-shell. The form factors obtained are very different but give the same coupling constant: g rho D*D* = 6.60 +/- 0.31. This number is 50% larger than what we would expect from SU(4) estimates. (c) 2007 Elsevier B.V. All rights reserved.

Pure spinor vertex operators in Siegel gauge and loop amplitude regularization

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Correspondence between the one-loop three-point vertex and the Y and Delta electric resistor networks

Different mathematical methods have been applied to obtain the analytic result for the massless triangle Feynman diagram yielding a sum of four linearly independent (LI) hypergeometric functions of two variables F-4. This result is not physically acceptable when it is embedded in higher loops, because all four hypergeometric functions in the triangle result have the same region of convergence and further integration means going outside those regions of convergence. We could go outside those regions by using the well-known analytic continuation formulas obeyed by the F-4, but there are at least two ways we can do this. Which is the correct one? Whichever continuation one uses, it reduces a number of F-4 from four to three. This reduction in the number of hypergeometric functions can be understood by taking into account the fundamental physical constraint imposed by the conservation of momenta flowing along the three legs of the diagram. With this, the number of overall LI functions that enter the most general solution must reduce accordingly. It remains to determine which set of three LI solutions needs to be taken. To determine the exact structure and content of the analytic solution for the three-point function that can be embedded in higher loops, we use the analogy that exists between Feynman diagrams and electric circuit networks, in which the electric current flowing in the network plays the role of the momentum flowing in the lines of a Feynman diagram. This analogy is employed to define exactly which three out of the four hypergeometric functions are relevant to the analytic solution for the Feynman diagram. The analogy is built based on the equivalence between electric resistance circuit networks of types Y and Delta in which flows a conserved current. The equivalence is established via the theorem of minimum energy dissipation within circuits having these structures.

Solving the minimum vertex floodlight problem with hybrid metaheuristics

In this paper we propose four approximation algorithms (metaheuristic based), for the Minimum Vertex Floodlight Set problem. Urrutia et al. [9] solved the combinatorial problem, although it is strongly believed that the algorithmic problem is NP-hard. We conclude that, on average, the minimum number of vertex floodlights needed to illuminate a orthogonal polygon with n vertices is n/4,29.

Computational solid mechanics using a vertex-based finite volume method

A number of research groups are now developing and using finite volume (FV) methods for computational solid mechanics (CSM). These methods are proving to be equivalent and in some cases superior to their finite element (FE) counterparts. In this paper we will describe a vertex-based FV method with arbitrarily structured meshes, for modelling the elasto-plastic deformation of solid materials undergoing small strains in complex geometries. Comparisons with rational FE methods will be given.

Smoothing a Discrete Hazard Function for the Number of Patients Colonized with Methicillin-Resistance Staphylococcus Aureus in an Intensive Care Unit

A new method for estimating the time to colonization of Methicillin-resistant Staphylococcus Aureus (MRSA) patients is developed in this paper. The time to colonization of MRSA is modelled using a Bayesian smoothing approach for the hazard function. There are two prior models discussed in this paper: the first difference prior and the second difference prior. The second difference prior model gives smoother estimates of the hazard functions and, when applied to data from an intensive care unit (ICU), clearly shows increasing hazard up to day 13, then a decreasing hazard. The results clearly demonstrate that the hazard is not constant and provide a useful quantification of the effect of length of stay on the risk of MRSA colonization which provides useful insight.

Particle number and mass emission factors from combustion of wood samples collected from Queensland forest

Knowledge of particle emission characteristics associated with forest fires and in general, biomass burning, is becoming increasingly important due to the impact of these emissions on human health. Of particular importance is developing a better understanding of the size distribution of particles generated from forest combustion under different environmental conditions, as well as provision of emission factors for different particle size ranges. This study was aimed at quantifying particle emission factors from four types of wood found in South East Queensland forests: Spotted Gum (Corymbia citriodora), Red Gum (Eucalypt tereticornis), Blood Gum (Eucalypt intermedia), and Iron bark (Eucalypt decorticans); under controlled laboratory conditions. The experimental set up included a modified commercial stove connected to a dilution system designed for the conditions of the study. Measurements of particle number size distribution and concentration resulting from the burning of woods with a relatively homogenous moisture content (in the range of 15 to 26 %) and for different rates of burning were performed using a TSI Scanning Mobility Particle Sizer (SMPS) in the size range from 10 to 600 nm and a TSI Dust Trak for PM2.5. The results of the study in terms of the relationship between particle number size distribution and different condition of burning for different species show that particle number emission factors and PM2.5 mass emission factors depend on the type of wood and the burning rate; fast burning or slow burning. The average particle number emission factors for fast burning conditions are in the range of 3.3 x 1015 to 5.7 x 1015 particles/kg, and for PM2.5 are in the range of 139 to 217 mg/kg.

Long-term trends in fine particle number concentrations in the urban atmosphere of Brisbane : the relevance of traffic emissions and new particle formation

The measurement of submicrometre (< 1.0 m) and ultrafine particles (diameter < 0.1 m) number concentration have attracted attention since the last decade because the potential health impacts associated with exposure to these particles can be more significant than those due to exposure to larger particles. At present, ultrafine particles are not regularly monitored and they are yet to be incorporated into air quality monitoring programs. As a result, very few studies have analysed their long-term and spatial variations in ultrafine particle concentration, and none have been in Australia. To address this gap in scientific knowledge, the aim of this research was to investigate the long-term trends and seasonal variations in particle number concentrations in Brisbane, Australia. Data collected over a five-year period were analysed using weighted regression models. Monthly mean concentrations in the morning (6:00-10:00) and the afternoon (16:00-19:00) were plotted against time in months, using the monthly variance as the weights. During the five-year period, submicrometre and ultrafine particle concentrations increased in the morning by 105.7% and 81.5% respectively whereas in the afternoon there was no significant trend. The morning concentrations were associated with fresh traffic emissions and the afternoon concentrations with the background. The statistical tests applied to the seasonal models, on the other hand, indicated that there was no seasonal component. The spatial variation in size distribution in a large urban area was investigated using particle number size distribution data collected at nine different locations during different campaigns. The size distributions were represented by the modal structures and cumulative size distributions. Particle number peaked at around 30 nm, except at an isolated site dominated by diesel trucks, where the particle number peaked at around 60 nm. It was found that ultrafine particles contributed to 82%-90% of the total particle number. At the sites dominated by petrol vehicles, nanoparticles (< 50 nm) contributed 60%-70% of the total particle number, and at the site dominated by diesel trucks they contributed 50%. Although the sampling campaigns took place during different seasons and were of varying duration these variations did not have an effect on the particle size distributions. The results suggested that the distributions were rather affected by differences in traffic composition and distance to the road. To investigate the occurrence of nucleation events, that is, secondary particle formation from gaseous precursors, particle size distribution data collected over a 13 month period during 5 different campaigns were analysed. The study area was a complex urban environment influenced by anthropogenic and natural sources. The study introduced a new application of time series differencing for the identification of nucleation events. To evaluate the conditions favourable to nucleation, the meteorological conditions and gaseous concentrations prior to and during nucleation events were recorded. Gaseous concentrations did not exhibit a clear pattern of change in concentration. It was also found that nucleation was associated with sea breeze and long-range transport. The implications of this finding are that whilst vehicles are the most important source of ultrafine particles, sea breeze and aged gaseous emissions play a more important role in secondary particle formation in the study area.

Year 6 students' idiosyncratic notions of unitising, reunitising and regrouping decimal number places

Having flexible notions of the unit (e.g., 26 ones can be thought of as 2.6 tens, 1 ten 16 ones, 260 tenths, etc.) should be a major focus of elementary mathematics education. However, often these powerful notions are relegated to computations where the major emphasis is on "getting the right answer" thus procedural knowledge rather than conceptual knowledge becomes the primary focus. This paper reports on 22 high-performing students' reunitising processes ascertained from individual interviews on tasks requiring unitising, reunitising and regrouping; errors were categorised to depict particular thinking strategies. The results show that, even for high-performing students, regrouping is a cognitively complex task. This paper analyses this complexity and draws inferences for teaching.

Development of a particle number and particle mass vehicle emissions inventory for an urban fleet

Motor vehicles are major emitters of gaseous and particulate pollution in urban areas, and exposure to particulate pollution can have serious health effects, ranging from respiratory and cardiovascular disease to mortality. Motor vehicle tailpipe particle emissions span a broad size range from 0.003-10µm, and are measured as different subsets of particle mass concentrations or particle number count. However, no comprehensive inventories currently exist in the international published literature covering this wide size range. This paper presents the first published comprehensive inventory of motor vehicle tailpipe particle emissions covering the full size range of particles emitted. The inventory was developed for urban South-East Queensland by combining two techniques from distinctly different disciplines, from aerosol science and transport modelling. A comprehensive set of particle emission factors were combined with traffic modelling, and tailpipe particle emissions were quantified for particle number (ultrafine particles), PM1, PM2.5 and PM10 for light and heavy duty vehicles and buses. A second aim of the paper involved using the data derived in this inventory for scenario analyses, to model the particle emission implications of different proportions of passengers travelling in light duty vehicles and buses in the study region, and to derive an estimate of fleet particle emissions in 2026. It was found that heavy duty vehicles (HDVs) in the study region were major emitters of particulate matter pollution, and although they contributed only around 6% of total regional vehicle kilometres travelled, they contributed more than 50% of the region’s particle number (ultrafine particles) and PM1 emissions. With the freight task in the region predicted to double over the next 20 years, this suggests that HDVs need to be a major focus of mitigation efforts. HDVs dominated particle number (ultrafine particles) and PM1 emissions; and LDV PM2.5 and PM10 emissions. Buses contributed approximately 1-2% of regional particle emissions.

Increase in particle number emissions from motor vehicles due to interruption of steady traffic flow

We assess the increase in particle number emissions from motor vehicles driving at steady speed when forced to stop and accelerate from rest. Considering the example of a signalized pedestrian crossing on a two-way single-lane urban road, we use a complex line source method to calculate the total emissions produced by a specific number and mix of light petrol cars and diesel passenger buses and show that the total emissions during a red light is significantly higher than during the time when the light remains green. Replacing two cars with one bus increased the emissions by over an order of magnitude. Considering these large differences, we conclude that the importance attached to particle number emissions in traffic management policies be reassessed in the future.

A genetic algorithm for the multi-source and multi-sink minimum vertex cut problem and its applications

We present a new penalty-based genetic algorithm for the multi-source and multi-sink minimum vertex cut problem, and illustrate the algorithm’s usefulness with two real-world applications. It is proved in this paper that the genetic algorithm always produces a feasible solution by exploiting some domain-specific knowledge. The genetic algorithm has been implemented on the example applications and evaluated to show how well it scales as the problem size increases.