Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Wireless Network-Coded Bidirectional Relaying Using Latin Squares for M-PSK Modulation

The design of modulation schemes for the physical layer network-coded two-way relaying scenario is considered with a protocol which employs two phases: multiple access (MA) phase and broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of MA interference which occurs at the relay during the MA phase and all these network coding maps should satisfy a requirement called the exclusive law. We show that every network coding map that satisfies the exclusive law is representable by a Latin Square and conversely, that this relationship can be used to get the network coding maps satisfying the exclusive law. The channel fade states for which the minimum distance of the effective constellation at the relay become zero are referred to as the singular fade states. For M - PSK modulation (M any power of 2), it is shown that there are (M-2/4 - M/2 + 1) M singular fade states. Also, it is shown that the constraints which the network coding maps should satisfy so that the harmful effects of the singular fade states are removed, can be viewed equivalently as partially filled Latin Squares (PFLS). The problem of finding all the required maps is reduced to finding a small set of maps for M - PSK constellations (any power of 2), obtained by the completion of PFLS. Even though the completability of M x M PFLS using M symbols is an open problem, specific cases where such a completion is always possible are identified and explicit construction procedures are provided. Having obtained the network coding maps, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map chosen in a particular region. It is shown that the complex plane can be partitioned into two regions: a region in which any network coding map which satisfies the exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for M = 4-PSK signal set by Koike-Akino et al., when specialized for Simulation results show that the proposed scheme performs better than the conventional exclusive-OR (XOR) network coding and in some cases outperforms the scheme proposed by Koike-Akino et al.

Wireless bidirectional relaying and Latin squares

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) Phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA Phase and all these network coding maps should satisfy a requirement called the exclusive law. We show that every network coding map that satisfies the exclusive law is representable by a Latin Square and conversely, and this relationship can be used to get the network coding maps satisfying the exclusive law. Using the structural properties of the Latin Squares for a given set of parameters, the problem of finding all the required maps is reduced to finding a small set of maps for M-PSK constellations. This is achieved using the notions of isotopic and transposed Latin Squares. Furthermore, the channel conditions for which the bit-wise XOR will perform well is analytically obtained which holds for all values of M (for M any power of 2). We illustrate these results for the case where both the end users use QPSK constellation.

Hydrodynamic instability and shear layer effect on the response of an acoustically excited laminar premixed flame

Combustion instabilities can cause serious problems which limit the operating envelope of low-emission lean premixed combustion systems. Predicting the onset of combustion instability requires a description of the unsteady heat release driving the instability, i.e., the heat release response transfer function of the system. This study focuses on the analysis of fully coupled two-way interactions between a disturbance field and a laminar premixed flame that incorporates gas expansion effects by solving the conservation equations of a compressible fluid. Results of the minimum and maximum flame front deflections are presented to underline the impact of the hydrodynamic instability on the flame and the shear layer effect on the initial flame front wrinkling which is increased at decreasing gas expansion. These phenomena influence the magnitude of the burning area and burning area rate response of the flame at lower frequency excitation more drastically than reduced-order model (ROM) predictions even for low temperature ratios. It is shown that the general trend of the flame response magnitudes can be well captured at higher frequency excitation, where stretch effects are dominant. The phase response is influenced by the DL mechanism, which cannot be captured by the ROM, and by the resulting discrepancy in the flame pocket formation and annihilation process at the flame tip. (C) 2014 The Combustion Institute. Published by Elsevier Inc. All rights reserved,

The Self-Association of Graphane Is Driven by London Dispersion and Enhanced Orbital Interactions

We investigated the nature of the cohesive energy between graphane sheets via multiple CH center dot center dot center dot HC interactions, using density functional theory (DFT) including dispersion correction (Grimmes D3 approach) computations of n]graphane sigma dimers (n = 6-73). For comparison, we also evaluated the binding between graphene sheets that display prototypical pi/pi interactions. The results were analyzed using the block-localized wave function (BLW) method, which is a variant of ab initio valence bond (VB) theory. BLW interprets the intermolecular interactions in terms of frozen interaction energy (Delta E-F) composed of electrostatic and Pauli repulsion interactions, polarization (Delta E-pol), charge-transfer interaction (Delta E-CT), and dispersion effects (Delta E-disp). The BLW analysis reveals that the cohesive energy between graphane sheets is dominated by two stabilizing effects, namely intermolecular London dispersion and two-way charge transfer energy due to the sigma CH -> sigma*(HC) interactions. The shift of the electron density around the nonpolar covalent C-H bonds involved in the intermolecular interaction decreases the C-H bond lengths uniformly by 0.001 angstrom. The Delta E-CT term, which accounts for similar to 15% of the total binding energy, results in the accumulation of electron density in the interface area between two layers. This accumulated electron density thus acts as an electronic glue for the graphane layers and constitutes an important driving force in the self-association and stability of graphane under ambient conditions. Similarly, the double faced adhesive tape style of charge transfer interactions was also observed among graphene sheets in which it accounts for similar to 18% of the total binding energy. The binding energy between graphane sheets is additive and can be expressed as a sum of CH center dot center dot center dot HC interactions, or as a function of the number of C-H bonds.

Interaction of a vortex ring with a single bubble: bubble and vorticity dynamics

The interaction of a single bubble with a single vortex ring in water has been studied experimentally. Measurements of both the bubble dynamics and vorticity dynamics have been done to help understand the two-way coupled problem. The circulation strength of the vortex ring (Gamma) has been systematically varied, while keeping the bubble diameter (D-b) constant, with the bubble volume to vortex core volume ratio (V-R) also kept fixed at about 0.1. The other important parameter in the problem is a Weber number based on the vortex ring strength. (We = 0.87 rho(Gamma/2 pi a)(2)/(sigma/D-b); a = vortex core radius, sigma = surface tension), which is varied over a large range, We = 3-406. The interaction between the bubble and ring for each of the We cases broadly falls into four stages. Stage I is before capture of the bubble by the ring where the bubble is drawn into the low-pressure vortex core, while in stage II the bubble is stretched in the azimuthal direction within the ring and gradually broken up into a number of smaller bubbles. Following this, in stage III the bubble break-up is complete and the resulting smaller bubbles slowly move around the core, and finally in stage IV the bubbles escape. Apart from the effect of the ring on the bubble, the bubble is also shown to significantly affect the vortex ring, especially at low We (We similar to 3). In these low-We cases, the convection speed drops significantly compared to the base case without a bubble, while the core appears to fragment with a resultant large decrease in enstrophy by about 50 %. In the higher-We cases (We > 100), there are some differences in convection speed and enstrophy, but the effects are relatively small. The most dramatic effects of the bubble on the ring are found for thicker core rings at low We (We similar to 3) with the vortex ring almost stopping after interacting with the bubble, and the core fragmenting into two parts. The present idealized experiments exhibit many phenomena also seen in bubbly turbulent flows such as reduction in enstrophy, suppression of structures, enhancement of energy at small scales and reduction in energy at large scales. These similarities suggest that results from the present experiments can be helpful in better understanding interactions of bubbles with eddies in turbulent flows.

ANRC Hybrid Test Bed Implementation and an End-to-End Performance Characterization of Dynamic Spectrum Access

An abundance of spectrum access and sensing algorithms are available in the dynamic spectrum access (DSA) and cognitive radio (CR) literature. Often, however, the functionality and performance of such algorithms are validated against theoretical calculations using only simulations. Both the theoretical calculations and simulations come with their attendant sets of assumptions. For instance, designers of dynamic spectrum access algorithms often take spectrum sensing and rendezvous mechanisms between transmitter-receiver pairs for granted. Test bed designers, on the other hand, either customize so much of their design that it becomes difficult to replicate using commercial off the shelf (COTS) components or restrict themselves to simulation, emulation /hardware-in-Ioop (HIL), or pure hardware but not all three. Implementation studies on test beds sophisticated enough to combine the three aforementioned aspects, but at the same time can also be put together using COTS hardware and software packages are rare. In this paper we describe i) the implementation of a hybrid test bed using a previously proposed hardware agnostic system architecture ii) the implementation of DSA on this test bed, and iii) the realistic hardware and software-constrained performance of DSA. Snapshot energy detector (ED) and Cumulative Summation (CUSUM), a sequential change detection algorithm, are available for spectrum sensing and a two-way handshake mechanism in a dedicated control channel facilitates transmitter-receiver rendezvous.