Efficient algorithms for computing Reeb graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. We describe an algorithm that constructs the Reeb graph of a Morse function defined on a 3-manifold. Our algorithm maintains connected components of the two dimensional levels sets as a dynamic graph and constructs the Reeb graph in O(nlogn+nlogg(loglogg)3) time, where n is the number of triangles in the tetrahedral mesh representing the 3-manifold and g is the maximum genus over all level sets of the function. We extend this algorithm to construct Reeb graphs of d-manifolds in O(nlogn(loglogn)3) time, where n is the number of triangles in the simplicial complex that represents the d-manifold. Our result is a significant improvement over the previously known O(n2) algorithm. Finally, we present experimental results of our implementation and demonstrate that our algorithm for 3-manifolds performs efficiently in practice.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

New algorithms of the Q-learning type

We propose two algorithms for Q-learning that use the two-timescale stochastic approximation methodology. The first of these updates Q-values of all feasible state–action pairs at each instant while the second updates Q-values of states with actions chosen according to the ‘current’ randomized policy updates. A proof of convergence of the algorithms is shown. Finally, numerical experiments using the proposed algorithms on an application of routing in communication networks are presented on a few different settings.

Interference Alignment Algorithms for the K User Constant MIMO Interference Channel

This paper considers the degrees of freedom (DOF) for a K user multiple-input multiple-output (MIMO) M x N interference channel using interference alignment (IA). A new performance metric for evaluating the efficacy of IA algorithms is proposed, which measures the extent to which the desired signal dimensionality is preserved after zero-forcing the interference at the receiver. Inspired by the metric, two algorithms are proposed for designing the linear precoders and receive filters for IA in the constant MIMO interference channel with a finite number of symbol extensions. The first algorithm uses an eigenbeamforming method to align sub-streams of the interference to reduce the dimensionality of the interference at all the receivers. The second algorithm is iterative, and is based on minimizing the interference leakage power while preserving the dimensionality of the desired signal space at the intended receivers. The improved performance of the algorithms is illustrated by comparing them with existing algorithms for IA using Monte Carlo simulations.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

The existence of homeomorphic subgraphs in chordal graphs

We establish conditions for the existence, in a chordal graph, of subgraphs homeomorphic to K-n (n greater than or equal to 3), K-m,K-n (m,n greater than or equal to 2), and wheels W-r (r greater than or equal to 3). Using these results, we develop a simple linear time algorithm for testing planarity of chordal graphs. We also show how these results lead to simple polynomial time algorithms for the Fixed Subgraph Homeomorphism problem on chordal graphs for some special classes of pattern graphs.

Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

Effect of substrate temperature on the physical properties of dc magnetron sputtered CuAlO2 films

Copper aluminum oxide films were prepared by direct current (dc) reactive magnetron sputtering under various substrate temperatures in the range of 303–648 K and systematically studied their physical properties. The physical properties of the films were strongly affected by the substrate temperature. The films formed at substrate temperatures <373 K were amorphous while those deposited at higher substrate temperatures (≥373 K) were polycrystalline in nature. The electrical properties of the films enhanced with substrate temperature due to the improved crystallinity. The Hall mobility of 9.4 cm2/V s and carrier concentration of 3.5 × 1017 cm−3 were obtained at the substrate temperature of 573 K. The optical band gap of the films decreased from 3.87 to 3.46 eV with the increase of substrate temperature from 373 to 573 K.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Role of Capping Ligands on the Nanoparticles in the Modulation of Properties of a Hybrid Matrix of Nanoparticles in a 2D Film and in a Supramolecular Organogel

We incorporate various gold nanoparticles (AuNPs) capped with different ligands in two-dimensional films and three-dimensional aggregates derived from N-stearoyl-L-alanine and N-lauroyl-L-alanine, respectively. The assemblies of N-stearoyl-L-alanine afforded stable films at the air-water interface. More compact assemblies were formed upon incorporation of AuNPs in the air-water interface of N-stearoyl-L-alanine. We then examined the effects of incorporation of various AuNPs functionalized with different capping ligands in three-dimensional assemblies of N-lauroyl-L-alanine, a compound that formed a gel in hydrocarbons. The profound influence of nanoparticle incorporation into physical gels was evident from evaluation of various microscopic and bulk properties. The interaction of AuNPs with the gelator assembly was found to depend critically on the capping ligands protecting the Au surface of the gold nanoparticles. Transmission electron microscopy (TEM) showed a long-range directional assembly of certain AuNPs along the gel fibers. Scanning electron microscopy (SEM) images of the freeze-dried gels and nanocomposites indicate that the morphological transformation in the composite microstructures depends significantly on the capping agent of the nanoparticles. Differential scanning calorimetry (DSC) showed that gel formation from sol occurred at a lower temperature upon incorporation of AuNPs having capping ligands that were able to align and noncovalently interact with the gel fibers. Rheological studies indicate that the gel-nanoparticle composites exhibit significantly greater viscoelasticity compared to the native gel alone when the capping ligands are able to interact through interdigitation into the gelator assembly. Thus, it was possible to define a clear relationship between the materials and the molecular-level properties by means of manipulation of the information inscribed on the NP surface.

Generic Routing Rules and a Scalable Access Enhancement for the Network-on-Chip RECONNECT

RECONNECT is a Network-on-Chip using a honeycomb topology. In this paper we focus on properties of general rules applicable to a variety of routing algorithms for the NoC which take into account the missing links of the honeycomb topology when compared to a mesh. We also extend the original proposal [5] and show a method to insert and extract data to and from the network. Access Routers at the boundary of the execution fabric establish connections to multiple periphery modules and create a torus to decrease the node distances. Our approach is scalable and ensures homogeneity among the compute elements in the NoC. We synthesized and evaluated the proposed enhancement in terms of power dissipation and area. Our results indicate that the impact of necessary alterations to the fabric is negligible and effects the data transfer between the fabric and the periphery only marginally.

Microstructure related influence on the electrical properties of pulsed laser ablated (Ba, Sr)TiO3 thin films

The microstructural dependence of electrical properties of (Ba, Sr)TiO3(BST) thin films were studied from the viewpoint of dc and ac electrical properties. The films were grown using a pulsed laser deposition technique in a temperature range of 300 to 600 degrees C, inducing changes in grain size, structure, and morphology. Consequently, two different types of films were realized, of which type I, was polycrystalline, multigrained, while type II was [100] oriented possessing a densely packed fibrous microstructure. Leakage current measurements were done at elevated temperatures to provide evidence of the conduction mechanism present in these films. The results revealed a contribution from both electronic and ionic conduction. In the case of type I films, two trapping levels were identified with energies around 0.5 and 2.73 eV, which possibly originate from oxygen vacancies V-O and Ti3+ centers, respectively. These levels act as shallow and deep traps and are reflected in the current-voltage characteristics of the BST thin films. The activation energy associated with oxygen vacancy motion in this case was obtained as 1.28 eV. On the contrary, type II films showed no evidence of deep trap energy levels, while the identified activation energy associated with shallow traps was obtained as 0.38 eV. The activation energy obtained for oxygen vacancy motion in type II films was around 1.02 eV. The dc measurement results were further elucidated through ac impedance analysis, which revealed a grain boundary dominated response in type I in comparison to type II films where grain response is highlighted. A comparison of the mean relaxation time of the two films revealed three orders of magnitude higher relaxation time in the case of type I films. Due to smaller grain size in type I films the grains were considered to be completely depleted giving rise to only grain boundary response for the bulk of the film. The activation energy obtained from conductivity plots agree very well with that of dc measurements giving values 1.3 and 1.07 eV for type I and type II films, respectively. Since oxygen vacancy transport have been identified as the origin of resistance degradation in BST thin films, type I films with their higher value of activation energy for oxygen ion mobility explains the improvement in breakdown characteristics under constant high dc field stress. The role of microstructure in controlling the rate of degradation is found useful in this instance to enhance the film properties under high electric field stresses. (C) 2000 American Institute of Physics. [S0021-8979(00)00418-7].

Purification and properties of trehalase from the thermophilic fungus Humicola lanuginosa

Trehalase (?,?-Trehalosee gludohydrolase, EC 3.2.1.28) was partially solubilized from the thermophilic fungus Humicola lanuginosa RM-B, and purified 184-fold. The purified enzyme was optimally active at 50°C in acetate buffer at pH 5.5. It was highly specific for ?,?-trehalose and had an apparent Km = 0.4 mM at 50°C. None of the other disaccharides tested either inhibited or activated the enzyme. The molecular weight of the enzyme was around 170000. Trehalase from mycelium grown at 40 and 50°C had similar properties. The purified enzyme, in contrast to that in the crude-cell free extract, was less stable. At low concentration, purified trehalase was afforded protection against heat-inactivation by �protective factor(s)� present in mycelial extracts. The �protective factor(s)� was sensitive to proteolytic digestion. It was not diffusable and was stable to boiling for at least 30 min. Bovine serum albumin and casein also protected the enzyme from heat-inactivation.