Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) over cap (u, v) of the actual distance d( u, v) between u, v is an element of V is said to be of stretch t if and only if delta(u, v) <= (delta) over cap (u, v) <= t . delta(u, v). Computing all-pairs small stretch distances efficiently ( both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24].

A Pd-6 Molecular Cage via Multicomponent Self-Assembly Incorporating Both Neutral and Anionic Linkers

A Pd-6 molecular cage [{(tmen)Pd}(6)(bpy)(3)(tma)2)](NO3)(6) [1; where tmen = N,N,N,N-tetramethylethylene diamine, bpy = 4,4'-bipyridyl,and H(3)tma = trimesic acid] was prepared via the template-free three-component seff-assembly of a cis-blocked palladium(II) acceptorin combination with a tricarboxylate and a dipyridyl donor. Complex 1 represents the first example of a 3D palladium(II) cage of defined shape incorporating anionic and neutral linkers. Guest-induced exclusive formation of this cage was also monitored by an NMR study.

Photoluminescence spectroscopy and lifetime measurements from self-assembled semiconductor-metal nanoparticle hybrid arrays

We present results of photoluminescence spectroscopy and lifetime measurements on thin film hybrid arrays of semiconductor quantum dots and metal nanoparticles embedded in a block copolymer template. The intensity of emission as well as the measured lifetime would be controlled by varying the volume fraction and location of gold nanoparticles in the matrix. We demonstrate the ability to both enhance and quench the luminescence in the hybrids as compared to the quantum dot array films while simultaneously engineering large reduction in luminescence lifetime with incorporation of gold nanoparticles. (C) 2010 American Institute of Physics. [doi:10.1063/1.3483162].

On Musical Self-Similarity : Intersemiosis as Synecdoche and Analogy

Self-similarity, a concept taken from mathematics, is gradually becoming a keyword in musicology. Although a polysemic term, self-similarity often refers to the multi-scalar feature repetition in a set of relationships, and it is commonly valued as an indication for musical coherence and consistency . This investigation provides a theory of musical meaning formation in the context of intersemiosis, that is, the translation of meaning from one cognitive domain to another cognitive domain (e.g. from mathematics to music, or to speech or graphic forms). From this perspective, the degree of coherence of a musical system relies on a synecdochic intersemiosis: a system of related signs within other comparable and correlated systems. This research analyzes the modalities of such correlations, exploring their general and particular traits, and their operational bounds. Looking forward in this direction, the notion of analogy is used as a rich concept through its two definitions quoted by the Classical literature: proportion and paradigm, enormously valuable in establishing measurement, likeness and affinity criteria. Using quantitative qualitative methods, evidence is presented to justify a parallel study of different modalities of musical self-similarity. For this purpose, original arguments by Benoît B. Mandelbrot are revised, alongside a systematic critique of the literature on the subject. Furthermore, connecting Charles S. Peirce s synechism with Mandelbrot s fractality is one of the main developments of the present study. This study provides elements for explaining Bolognesi s (1983) conjecture, that states that the most primitive, intuitive and basic musical device is self-reference, extending its functions and operations to self-similar surfaces. In this sense, this research suggests that, with various modalities of self-similarity, synecdochic intersemiosis acts as system of systems in coordination with greater or lesser development of structural consistency, and with a greater or lesser contextual dependence.

Constructing Reeb Graphs using Cylinder Maps

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. In this video, we describe a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Arcs in the Reeb graph are computed in the second step using a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The algorithm is also able to handle non-manifold domains.

Examining effectiveness of an immigrant labor market integration intervention. The role of acculturation, discrimination, self-efficacy, outcome expectances, action and coping planning.

The designing of effective intervention tools to improve immigrants’ labor market integration remains an important topic in contemporary Western societies. This study examines whether and how a new intervention tool, Working Life Certificate (WLC), helps unemployed immigrants to find employment and strengthen their belief of their vocational skills. The study is based on quantitative longitudinal survey data from 174 unemployed immigrants of various origins who participated in the pilot phase of WLC examinations in 2009. Surveys were administered in three waves: before the test, right after it, and three months later. Although it is often argued that the unemployment among immigrants is due either to their lack of skills and cultural differences or to discrimination in recruitment, scholars within social psychology of behavior change argue that the best way of helping people to achieve their goals (e.g. finding employment) is to build up their sense of self-efficacy, alter their outcome expectances in a more positive direction or to help them to construct more detailed action and coping plans. This study aims to shed light on the role of these concepts in immigrants’ labor market integration. The results support the theories of behavior change moderately. Having positive expectances regarding the outcomes of various job search behaviors was found to predict employment in the future. Together with action and coping planning it also predicted increase in job search behavior. The intervention, WLC, was able to affect participants’ self-efficacy, but contrary to expectations, self-efficacy was found not to be related to either job search behavior or future labor market status. Also, perceived discrimination did not explain problems in finding employment, but hints of subtle or structural discrimination were found. Adoption of Finnish work culture together with strong family culture was found to predict future employment. Hence, in this thesis I argue that awarding people diplomas should be preferred in immigrant integration training as it strengthens people’s sense of self-efficacy. Instead of teaching new information, more attention should be directed at changing people’s outcome expectances in a more positive direction and helping them to construct detailed plans on how to achieve their goals.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

Controlled photoluminescence from self-assembled semiconductor-metal quantum dot hybrid array films

Thin films of hybrid arrays of cadmium selenide quantum dots and polymer grafted gold nanoparticles have been prepared using a BCP template. Controlling the dispersion and location of the respective nanoparticles allows us to tune the exciton-plasmon interaction in such hybrid arrays and hence control their optical properties. The observed photoluminescence of the hybrid array films is interpreted in terms of the dispersion and location of the gold nanoparticles and quantum dots in the block copolymer matrix.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Self-assembled flower-like nanostructures of InN and GaN grown by plasma-assisted molecular beam epitaxy

Nanosized hexagonal InN flower-like structures were fabricated by droplet epitaxy on GaN/Si(111) and GaN flower-like nanostructure fabricated directly on Si(111) substrate using radio frequency plasma-assisted molecular beam epitaxy. Powder X-ray diffraction (XRD) and scanning electron microscopy (SEM) were used to study the crystallinity and morphology of the nanostructures. Moreover, X-ray photoelectron spectroscopy (XPS) and photoluminescence (PL) were used to investigate the chemical compositions and optical properties of nano-flowers, respectively. Activation energy of free exciton transitions in GaN nano-flowers was derived to be similar to 28.5 meV from the temperature dependent PL studies. The formation process of nano-flowers is investigated and a qualitative mechanism is proposed.

Impact of energy quantisation in single electron transistor island on hybrid complementary metal oxide semiconductor-single electron transistor integrated circuits

For the first time, the impact of energy quantisation in single electron transistor (SET) island on the performance of hybrid complementary metal oxide semiconductor (CMOS)-SET transistor circuits has been studied. It has been shown through simple analytical models that energy quantisation primarily increases the Coulomb Blockade area and Coulomb Blockade oscillation periodicity of the SET device and thus influences the performance of hybrid CMOS-SET circuits. A novel computer aided design (CAD) framework has been developed for hybrid CMOS-SET co-simulation, which uses Monte Carlo (MC) simulator for SET devices along with conventional SPICE for metal oxide semiconductor devices. Using this co-simulation framework, the effects of energy quantisation have been studied for some hybrid circuits, namely, SETMOS, multiband voltage filter and multiple valued logic circuits. Although energy quantisation immensely deteriorates the performance of the hybrid circuits, it has been shown that the performance degradation because of energy quantisation can be compensated by properly tuning the bias current of the current-biased SET devices within the hybrid CMOS-SET circuits. Although this study is primarily done by exhaustive MC simulation, effort has also been put to develop first-order compact model for SET that includes energy quantisation effects. Finally, it has been demonstrated that one can predict the SET behaviour under energy quantisation with reasonable accuracy by slightly modifying the existing SET compact models that are valid for metallic devices having continuous energy states.

Criticality of the exponential rate of decay for the largest nearest-neighbor link in random geometric graphs

Let n points be placed independently in d-dimensional space according to the density f(x) = A(d)e(-lambda parallel to x parallel to alpha), lambda, alpha > 0, x is an element of R-d, d >= 2. Let d(n) be the longest edge length of the nearest-neighbor graph on these points. We show that (lambda(-1) log n)(1-1/alpha) d(n) - b(n) converges weakly to the Gumbel distribution, where b(n) similar to ((d - 1)/lambda alpha) log log n. We also prove the following strong law for the normalized nearest-neighbor distance (d) over tilde (n) = (lambda(-1) log n)(1-1/alpha) d(n)/log log n: (d - 1)/alpha lambda <= lim inf(n ->infinity) (d) over tilde (n) <= lim sup(n ->infinity) (d) over tilde (n) <= d/alpha lambda almost surely. Thus, the exponential rate of decay alpha = 1 is critical, in the sense that, for alpha > 1, d(n) -> 0, whereas, for alpha <= 1, d(n) -> infinity almost surely as n -> infinity.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.