DETERMINISTIC ALGORITHMS FOR MATCHING AND PACKING PROBLEMS BASED ON REPRESENTATIVE SETS

In this work, we study the well-known r-DIMENSIONAL k-MATCHING ((r, k)-DM), and r-SET k-PACKING ((r, k)-SP) problems. Given a universe U := U-1 ... U-r and an r-uniform family F subset of U-1 x ... x U-r, the (r, k)-DM problem asks if F admits a collection of k mutually disjoint sets. Given a universe U and an r-uniform family F subset of 2(U), the (r, k)-SP problem asks if F admits a collection of k mutually disjoint sets. We employ techniques based on dynamic programming and representative families. This leads to a deterministic algorithm with running time O(2.851((r-1)k) .vertical bar F vertical bar. n log(2)n . logW) for the weighted version of (r, k)-DM, where W is the maximum weight in the input, and a deterministic algorithm with running time O(2.851((r-0.5501)k).vertical bar F vertical bar.n log(2) n . logW) for the weighted version of (r, k)-SP. Thus, we significantly improve the previous best known deterministic running times for (r, k)-DM and (r, k)-SP and the previous best known running times for their weighted versions. We rely on structural properties of (r, k)-DM and (r, k)-SP to develop algorithms that are faster than those that can be obtained by a standard use of representative sets. Incorporating the principles of iterative expansion, we obtain a better algorithm for (3, k)-DM, running in time O(2.004(3k).vertical bar F vertical bar . n log(2)n). We believe that this algorithm demonstrates an interesting application of representative families in conjunction with more traditional techniques. Furthermore, we present kernels of size O(e(r)r(k-1)(r) logW) for the weighted versions of (r, k)-DM and (r, k)-SP, improving the previous best known kernels of size O(r!r(k-1)(r) logW) for these problems.

Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

Effect of substitution on molecular conformation and packing features in a series of aryl substituted ethyl-6-methyl-4-phenyl-2-thioxo-1,2,3,4-tetrahydropyrimidine-5-carboxylates

The supramolecular structures of eight aryl protected ethyl-6-methyl-4-phenyl-2-thioxo-1,2,3,4 tetrahydropyrimidine-5-carboxyl ates were analyzed in order to understand the effect of variations in functional groups on molecular geometry, conformation and packing of molecules in the crystalline lattice. It is observed that the existence of a short intra-molecular C-H center dot center dot center dot pi interaction between the aromatic hydrogen of the aryl ring with the isolated double bond of the six-membered tetrahydropyrimidine ring is a key feature which imparts additional stability to the molecular conformation in the solid state. The compounds pack via the cooperative involvement of both N-H center dot center dot center dot S=C and N-H center dot center dot center dot O=C intermolecular dimers forming a sheet like structure. In addition, weak C-H center dot center dot center dot O and C-H center dot center dot center dot pi intermolecular interactions provide additional stability to the crystal packing.

New measures for estimating surface complementarity and packing at protein-protein interfaces

A number of methods exist that use different approaches to assess geometric properties like the surface complementarity and atom packing at the protein-protein interface. We have developed two new and conceptually different measures using the Delaunay tessellation and interface slice selection to compute the surface complementarity and atom packing at the protein-protein interface in a straightforward manner. Our measures show a strong correlation among themselves and with other existing measures, and can be calculated in a highly time-efficient manner. The measures are discriminative for evaluating biological, as well as non-biological protein-protein contacts, especially from large protein complexes and large-scale structural studies(http://pallab.serc. iisc.ernet.in/nip_nsc). (C) 201 Federation of European Biochemical Societies. Published by Elsevier B. V. All rights reserved.

On the ignition and extinction problems in forced convection systems

In this paper the problem of ignition and extinction has been formulated for the flow of a compressible fluid with Prandtl and Schmidt numbers taken as unity. In particular, the problems of (i) a jet impinging on a wall of combustible material and (ii) the opposed jet diffusion flame have been studied. In the wall jet case, three approximations in the momentum equation namely, (i) potential flow, (ii) viscous flow, (ii) viscous incompressible with k = 1 and (iii) Lees' approximation (taking pressure gradient terms zero) are studied. It is shown that the predictions of the mass flow rates at extinction are not very sensitive to the approximations made in the momentum equation. The effects of varying the wall temperature in the case (i) and the jet temperature in the case (ii) on the extinction speeds have been studied. The effects of varying the activation energy and the free stream oxidant concentration in case (ii), have also been investigated.

On some results of A. E. Livingston and coefficient problems for concave univalent functions

We consider functions that map the open unit disc conformally onto the complement of a bounded convex set. We call these functions concave univalent functions. In 1994, Livingston presented a characterization for these functions. In this paper, we observe that there is a minor flaw with this characterization. We obtain certain sharp estimates and the exact set of variability involving Laurent and Taylor coefficients for concave functions. We also present the exact set of variability of the linear combination of certain successive Taylor coefficients of concave functions.

Insights into conformational and packing features in a series of aryl substituted ethyl-6-methyl-4-phenyl-2-oxo-1,2,3,4-tetrahydropyrimidine-5-carboxylate

The supramolecular structures of eight aryl protected ethyl-6-methyl-4-phenyl-2-oxo-1,2,3,4-tetrahydropyrimidine- 5-carboxylates have been analyzed to determine the role of different functional groups on the molecular geometry, conformational characteristics and the packing of these molecules in the crystal lattice. Out of these the para fluoro substituted compound on the aryl ring exhibits conformational polymorphism, due to the different conformation of the ester moiety. This behaviour has been characterized using both powder and single-crystal X-ray diffraction, optical microscopy and differential scanning calorimetry performed on both these polymorphs. The compounds pack via the cooperative interplay of strong N-H center dot center dot center dot O=C intermolecular dimers and chains forming a sheet like structure. In addition, weak C-H center dot center dot center dot O=C and C-H center dot center dot center dot pi interactions impart additional stability to the crystal packing.

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.

Scattering theory and linear optimal control: Regulator and servo problems

In this paper, several known computational solutions are readily obtained in a very natural way for the linear regulator, fixed end-point and servo-mechanism problems using a certain frame-work from scattering theory. The relationships between the solutions to the linear regulator problem with different terminal costs and the interplay between the forward and backward equations have enabled a concise derivation of the partitioned equations, the forward-backward equations, and Chandrasekhar equations for the problem. These methods have been extended to the fixed end-point, servo, and tracking problems.

Analysis of designed beta-hairpin peptides: molecular conformation and packing in crystals

The crystal structures of several designed peptide hairpins have been determined in order to establish features of molecular conformations and modes of aggregation in the crystals. Hairpin formation has been induced using a centrally positioned (D)Pro-Xxx segment (Xxx = (L)Pro, Aib, Ac(6)c, Ala; Aib = alpha-aminoisobutyric acid; Ac(6)c = 1-aminocyclohexane-1-carboxylic acid). Structures of the peptides Boc-Leu-Phe-Val-(D)Pro-(L)Pro-Leu-Phe-Val-OMe (1), Boc-Leu-Tyr-Val-(D)Pro-(L)Pro-Leu-Phe-Val-OMe (2, polymorphic forms labeled as 2a and 2b), Boc-Leu-Val-Val-(D)Pro-(L)Pro-Leu-Val-Val-OMe (3), Boc-Leu-Phe-Val-(D)Pro-Aib-Leu-Phe-Val-OMe (4, polymorphic forms labeled as 4a and 4b), Boc-Leu-Phe-Val-(D)Pro-Ac(6)c-Leu-Phe-Val-OMe (5) and Boc-Leu-Phe-Val-(D)Pro-Ala-Leu-Phe-Val-OMe (6) are described. All the octapeptides adopt type II' beta-turn nucleated hairpins, stabilized by three or four cross-strand intramolecular hydrogen bonds. The angle of twist between the two antiparallel strands lies in the range of -9.8 degrees to -26.7 degrees. A detailed analysis of packing motifs in peptide hairpin crystals is presented, revealing three broad modes of association: parallel packing, antiparallel packing and orthogonal packing. An attempt to correlate aggregation modes in solution with observed packing motifs in crystals has been made by indexing of crystal faces in the case of three of the peptide hairpins. The observed modes of hairpin aggregation may be of relevance in modeling multiple modes of association, which may provide insights into the structure of insoluble polypeptide aggregates.

A finite element method for the Saint-Venant torsion and bending problems for prismatic beams

In this work, we present a finite element formulation for the Saint-Venant torsion and bending problems for prismatic beams. The torsion problem formulation is based on the warping function, and can handle multiply-connected regions (including thin-walled structures), compound and anisotropic bars. Similarly, the bending formulation, which is based on linearized elasticity theory, can handle multiply-connected domains including thin-walled sections. The torsional rigidity and shear centers can be found as special cases of these formulations. Numerical results are presented to show the good coarse-mesh accuracy of both the formulations for both the displacement and stress fields. The stiffness matrices and load vectors (which are similar to those for a variable body force in a conventional structural mechanics problem) in both formulations involve only domain integrals, which makes them simple to implement and computationally efficient. (C) 2014 Elsevier Ltd. All rights reserved.

Achieving sustainable transportation system for Indian cities - problems and issues

This article aims at identifying the research issues and challenges that need to be addressed to achieve sustainable transportation system for Indian cities. The same is achieved by understanding the current system and trends of urbanization, motorization and modal shares in India; and their impact on mobility and safety (the two basic goals of transportation) as well as environment. Further, the article explores the efforts by the central and state governments in India to address the sustainability issues, and the problems and issues over and above the present efforts to achieve sustainability. The article concludes by summarizing the research issues with respect to planning/modelling, non-motorized transport, public transport, driver behaviour and road safety and traffic management. It is expected that these research issues will provide potential directions for carrying out further research aimed at achieving sustainable transport system for Indian cities.

Studies in crystal engineering: Crystal packing, topological photodimerization and structure-reactivity correlations in fluoro-substituted styrylcoumarins

In continuation of our studies on the influence of fluoro substitution on the solid state photobehaviour and packing pattern of styrylcoumarins, the results obtained for 4-(3-fluorostyryl)coumarin 1, 4-styryl-6-fluorocoumarin 2 and 4-styryl-7-fluorocoumarin 3 are presented. The configuration of the dimers was established on the basis of crystal packing of 1 and 2 (alpha-packed). A rationale for the significantly lower dimer yield in the crystal for 2 is proposed. In the observed centrosymmetric arrangement of the reactants the C=O ...pi (phenyl) contacts seem to provide additional attractive interactions. C-H ... O and C-H ... F hydrogen bonding seems to provide stability in these structures.

Crystal packing and melting temperatures of small oxalate esters: the role of C-H center dot center dot center dot O hydrogen bonding

The simple dialkyl oxalates are generally liquids at room temperature except for dimethyl and di-tert-butyl oxalate which melt at 327 and 343 K. The crystal structures of diethyl, di-iso-propyl, di-n-butyl, di-tert-butyl and methyl ethyl oxalates were determined. The liquid esters were crystallized using the cryocrystallization technique. A comparison of the intermolecular interactions and packing features in these crystal structures was carried out. The crystal structure of dimethyl oxalate was redetermined at various temperatures. The other compounds were also studied at several temperatures in order to assess the attractive nature of the hydrogen bonds therein. A number of moderate to well defined C-H center dot center dot center dot O interactions account for the higher melting points of the two solid esters. Additionally, a diminished entropic contribution Delta S(m) in di-tert-butyl oxalate possibly increases the melting point of this compound further.

A comparative study of multiple attribute tree and inverted file structures for large bibliographic files

A variety of data structures such as inverted file, multi-lists, quad tree, k-d tree, range tree, polygon tree, quintary tree, multidimensional tries, segment tree, doubly chained tree, the grid file, d-fold tree. super B-tree, Multiple Attribute Tree (MAT), etc. have been studied for multidimensional searching and related problems. Physical data base organization, which is an important application of multidimensional searching, is traditionally and mostly handled by employing inverted file. This study proposes MAT data structure for bibliographic file systems, by illustrating the superiority of MAT data structure over inverted file. Both the methods are compared in terms of preprocessing, storage and query costs. Worst-case complexity analysis of both the methods, for a partial match query, is carried out in two cases: (a) when directory resides in main memory, (b) when directory resides in secondary memory. In both cases, MAT data structure is shown to be more efficient than the inverted file method. Arguments are given to illustrate the superiority of MAT data structure in an average case also. An efficient adaptation of MAT data structure, that exploits the special features of MAT structure and bibliographic files, is proposed for bibliographic file systems. In this adaptation, suitable techniques for fixing and ranking of the attributes for MAT data structure are proposed. Conclusions and proposals for future research are presented.