Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Alloying induced degradation of the absorption edge of InAsxSb1-x

InAsxSb1−x alloys show a strong bowing in the energy gap, the energy gap of the alloy can be less than the gap of the two parent compounds. The authors demonstrate that a consequence of this alloying is a systematic degradation in the sharpness of the absorption edge. The alloy disorder induced band-tail (Urbach tail) characteristics are quantitatively studied for InAs0.05Sb0.95.

Microscopic study of the 2/5 fractional quantum Hall edge

This paper reports on our study of the edge of the 2/5 fractional quantum Hall state, which is more complicated than the edge of the 1/3 state because of the presence of edge sectors corresponding to different partitions of composite fermions in the lowest two Lambda levels. The addition of an electron at the edge is a nonperturbative process and it is not a priori obvious in what manner the added electron distributes itself over these sectors. We show, from a microscopic calculation, that when an electron is added at the edge of the ground state in the [N(1), N(2)] sector, where N(1) and N(2) are the numbers of composite fermions in the lowest two Lambda levels, the resulting state lies in either [N(1) + 1, N(2)] or [N(1), N(2) + 1] sectors; adding an electron at the edge is thus equivalent to adding a composite fermion at the edge. The coupling to other sectors of the form [N(1) + 1 + k, N(2) - k], k integer, is negligible in the asymptotically low-energy limit. This study also allows a detailed comparison with the two-boson model of the 2/5 edge. We compute the spectral weights and find that while the individual spectral weights are complicated and nonuniversal, their sum is consistent with an effective two-boson description of the 2/5 edge.

Acyclic edge coloring of 2-degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph is called 2-degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2-degenerate graphs properly contains seriesparallel graphs, outerplanar graphs, non - regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a'(G)<=Delta + 2, where Delta = Delta(G) denotes the maximum degree of the graph. We prove the conjecture for 2-degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2-degenerate graph with maximum degree ?, then a'(G)<=Delta + 1. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 68:1-27, 2011

XPS and x-ray absorption-edge studies of the surface and bulk valence states of cerium in ceco2

XPS and LIII X-ray absorption edge studies regarding the valence state of cerium have been carried out on the intermetallic compounds CeCo2, which becomes superconducting at low temperatures. It is observed from XPS that the surface shows both Ce3+ and Ce4+ valence states, while the X-ray absorption edge studies reveal only Ce4+ in the bulk. Thus valence fluctuation and superconductivity do not coexist in the bulk of this compound.

Polymer based photo detectors

Recent developments in our laboratory related to polymer-based light sensors are reviewed. The inherent processibility of the active polymer medium is utilized in the implementation of different designs for the opto-electronic applications. The utility of these devices as sensitive photodetectors, image sensors and position sensitive detectors is demonstrated. The schottky-type layer formation at interfaces of polymers such as polyalkylthiophenes and aluminum accompanied by the enhanced photo-induced charge separation due to high local electric field is tapped for some of these device structures. The sensitivity of polymer-based field effect transistors to light also provides a convenient lateral geometry for efficient optical-coupling and control of the transistor state. ne range of these polymer-detectors available with the option of operating in the diode and transistor modes should be an attractive feature for many potential applications.

Fermi-edge singularity in photoluminescence spectra of modulation-doped AlGaAs/InGaAs/GaAs quantum wells

The photoluminescence study of Fermi-edge singularity (FES) in modulation-doped pseudomorphic AlxGa1-xAs/InyGa1-yAs/GaAs quantum well (QW) heterostructures is presented. In the above QW structures the optical transitions between n = 1 and n = 2 electronic subband to the n = 1 heavy hole subband (E-11 and E-21 transitions, respectively) are observed with FES appearing as a lower energy shoulder to the E-21 transition. The observed FES is attributed to the Fermi wave vector in the first electronic subband under the conditions of population of the second electronic subband. The FES appears at about 10 meV below E-21 transition around 4.2 K. Initially it gets stronger with increasing temperature and becomes a distinct peak at about 20 K. Further increase in temperature quenches FES and reaches the base line at around 40 K.

Effect of the Edge Type and Strain on the Structural, Electronic and Magnetic Properties of the BNRs

We present the effect of edge structures on the edge energy and stress of BN nanoribbons. Ab initio density functional calculations show that the armchair edge is lower in energy than the zigzag edge by 0.43 eV/angstrom. Both types of the edges are under the compressive stress. The zigzag edges are mechanically more stable than the armchair edges. Based on the calculated edge energies, the equilibrium shape of the BN flakes are found to be regular hexagonal, and dominated by the armchair edges. The zigzag ribbons are found to be half-metallic, whereas the armchair ribbons are semiconducting.

Continuum theory of edge states of topological insulators: variational principle and boundary conditions

We develop a continuum theory to model low energy excitations of a generic four-band time reversal invariant electronic system with boundaries. We propose a variational energy functional for the wavefunctions which allows us to derive natural boundary conditions valid for such systems. Our formulation is particularly suited for developing a continuum theory of the protected edge/surface excitations of topological insulators both in two and three dimensions. By a detailed comparison of our analytical formulation with tight binding calculations of ribbons of topological insulators modelled by the Bernevig-Hughes-Zhang (BHZ) Hamiltonian, we show that the continuum theory with a natural boundary condition provides an appropriate description of the low energy physics.

Mesh Simplification Based on Edge Collapsing Could Improve Computational Efficiency in Near Infrared Optical Tomographic Imaging

The diffusion equation-based modeling of near infrared light propagation in tissue is achieved by using finite-element mesh for imaging real-tissue types, such as breast and brain. The finite-element mesh size (number of nodes) dictates the parameter space in the optical tomographic imaging. Most commonly used finite-element meshing algorithms do not provide the flexibility of distinct nodal spacing in different regions of imaging domain to take the sensitivity of the problem into consideration. This study aims to present a computationally efficient mesh simplification method that can be used as a preprocessing step to iterative image reconstruction, where the finite-element mesh is simplified by using an edge collapsing algorithm to reduce the parameter space at regions where the sensitivity of the problem is relatively low. It is shown, using simulations and experimental phantom data for simple meshes/domains, that a significant reduction in parameter space could be achieved without compromising on the reconstructed image quality. The maximum errors observed by using the simplified meshes were less than 0.27% in the forward problem and 5% for inverse problem.

Magnetic-field-induced Fabry-Perot resonances in helical edge states

We study electronic transport across a helical edge state exposed to a uniform magnetic ((B) over right arrow) field over a finite length. We show that this system exhibits Fabry-Perot-type resonances in electronic transport. The intrinsic spin anisotropy of the helical edge states allows us to tune these resonances by changing the direction of the (B) over right arrow field while keeping its magnitude constant. This is in sharp contrast to the case of nonhelical one-dimensional electron gases with a parabolic dispersion, where similar resonances do appear in individual spin channels (up arrow and down arrow) separately which, however, cannot be tuned by merely changing the direction of the (B) over right arrow field. These resonances provide a unique way to probe the helical nature of the theory. We study the robustness of these resonances against a possible static impurity in the channel.

Methane and carbon dioxide adsorption on edge-functionalized graphene: a comparative DFT study

With a view towards optimizing gas storage and separation in crystalline and disordered nanoporous carbon-based materials, we use ab initio density functional theory calculations to explore the effect of chemical functionalization on gas binding to exposed edges within model carbon nanostructures. We test the geometry, energetics, and charge distribution of in-plane and out-of-plane binding of CO2 and CH4 to model zigzag graphene nanoribbons edge-functionalized with COOH, OH, NH2, H2PO3, NO2, and CH3. Although different choices for the exchange-correlation functional lead to a spread of values for the binding energy, trends across the functional groups are largely preserved for each choice, as are the final orientations of the adsorbed gas molecules. We find binding of CO2 to exceed that of CH4 by roughly a factor of two. However, the two gases follow very similar trends with changes in the attached functional group, despite different molecular symmetries. Our results indicate that the presence of NH2, H2PO3, NO2, and COOH functional groups can significantly enhance gas binding, making the edges potentially viable binding sites in materials with high concentrations of edge carbons. To first order, in-plane binding strength correlates with the larger permanent and induced dipole moments on these groups. Implications for tailoring carbon structures for increased gas uptake and improved CO2/CH4 selectivity are discussed. (C) 2012 American Institute of Physics. http://dx.doi.org/10.1063/1.4736568]