Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Rational design of 3D dendritic TiO2 nanostructures with favorable architectures

Controlling the morphology and size of titanium dioxide (TiO2) nanostructures is crucial to obtain superior photocatalytic, photovoltaic, and electrochemical properties. However, the synthetic techniques for preparing such structures, especially those with complex configurations, still remain a challenge because of the rapid hydrolysis of Ti-containing polymer precursors in aqueous solution. Herein, we report a completely novel approach-three- dimensional (3D) TiO2 nanostructures with favorable dendritic architectures-through a simple hydrothermal synthesis. The size of the 3D TiO2 dendrites and the morphology of the constituent nano-units, in the form of nanorods, nanoribbons, and nanowires, are controlled by adjusting the precursor hydrolysis rate and the surfactant aggregation. These novel configurations of TiO2 nanostructures possess higher surface area and superior electrochemical properties compared to nanoparticles with smooth surfaces. Our findings provide an effective solution for the synthesis of complex TiO2 nano-architectures, which can pave the way to further improve the energy storage and energy conversion efficiency of TiO 2-based devices.

DMT of Multi-hop Cooperative Networks-Part I: K-Parallel-Path Networks

We consider single-source, single-sink multi-hop relay networks, with slow-fading Rayleigh fading links and single-antenna relay nodes operating under the half-duplex constraint. While two hop relay networks have been studied in great detail in terms of the diversity-multiplexing tradeoff (DMT), few results are available for more general networks. In this two-part paper, we identify two families of networks that are multi-hop generalizations of the two hop network: K-Parallel-Path (KPP) networks and Layered networks. In the first part, we initially consider KPP networks, which can be viewed as the union of K node-disjoint parallel paths, each of length > 1. The results are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the optimal DMT of KPP(D) networks with K >= 4, and KPP(I) networks with K >= 3. Along the way, we derive lower bounds for the DMT of triangular channel matrices, which are useful in DMT computation of various protocols. As a special case, the DMT of two-hop relay network without direct link is obtained. Two key implications of the results in the two-part paper are that the half-duplex constraint does not necessarily entail rate loss by a factor of two, as previously believed and that, simple AF protocols are often sufficient to attain the best possible DMT.

Compiler-assisted instruction decoder energy optimization for clustered VLIW architectures

Traditionally, an instruction decoder is designed as a monolithic structure that inhibit the leakage energy optimization. In this paper, we consider a split instruction decoder that enable the leakage energy optimization. We also propose a compiler scheduling algorithm that exploits instruction slack to increase the simultaneous active and idle duration in instruction decoder. The proposed compiler-assisted scheme obtains a further 14.5% reduction of energy consumption of instruction decoder over a hardware-only scheme for a VLIW architecture. The benefits are 17.3% and 18.7% in the context of a 2-clustered and a 4-clustered VLIW architecture respectively.

Performance estimation of streaming applications for hierarchical MPSoCs

Parallel programming and effective partitioning of applications for embedded many-core architectures requires optimization algorithms. However, these algorithms have to quickly evaluate thousands of different partitions. We present a fast performance estimator embedded in a parallelizing compiler for streaming applications. The estimator combines a single execution-based simulation and an analytic approach. Experimental results demonstrate that the estimator has a mean error of 2.6% and computes its estimation 2848 times faster compared to a cycle accurate simulator.

Privacy architectures in social networks’ state-of-the-art survey

The use of social networking has exploded, with millions of people using various web- and mobile-based services around the world. This increase in social networking use has led to user anxiety related to privacy and the unauthorised exposure of personal information. Large-scale sharing in virtual spaces means that researchers, designers and developers now need to re-consider the issues and challenges of maintaining privacy when using social networking services. This paper provides a comprehensive survey of the current state-of-the-art privacy in social networks for both desktop and mobile uses and devices from various architectural vantage points. The survey will assist researchers and analysts in academia and industry to move towards mitigating many of the privacy issues in social networks.

Parallel implementation of AutoDock

Computational docking of ligands to protein structures is a key step in structure-based drug design. Currently, the time required for each docking run is high and thus limits the use of docking in a high-throughput manner, warranting parallelization of docking algorithms. AutoDock, a widely used tool, has been chosen for parallelization. Near-linear increases in speed were observed with 96 processors, reducing the time required for docking ligands to HIV-protease from 81 min, as an example, on a single IBM Power-5 processor ( 1.65 GHz), to about 1 min on an IBM cluster, with 96 such processors. This implementation would make it feasible to perform virtual ligand screening using AutoDock.

Monoclinic polymorph of Boc-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe(anhydrous). Parallel packing of 3(10)-/alpha-helices and a transition of helix type

The structures of two crystal forms of Boc-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe have been determined. The triclinic form (P1, Z = 1) from DMSO/H2O crystallizes as a dihydrate (Karle, Sukumar & Balaram (1986) Proc, Natl, Acad. Sci. USA 83, 9284-9288). The monoclinic form (P2(1), Z = 2) crystallized from dioxane is anhydrous. The conformation of the peptide is essentially the same in both crystal system, but small changes in conformational angles are associated with a shift of the helix from a predominantly alpha-type to a predominantly 3(10)-type. The r.m.s. deviation of 33 atoms in the backbone and C beta positions of residues 2-8 is only 0.29 A between molecules in the two polymorphs. In both space groups, the helical molecules pack in a parallel fashion, rather than antiparallel. The only intermolecular hydrogen bonding is head-to-tail between helices. There are no lateral hydrogen bonds. In the P2(1) cell, a = 9.422(2) A, b = 36.392(11) A, c = 10.548(2) A, beta = 111.31(2) degrees and V = 3369.3 A for 2 molecules of C60H97N11O13 per cell.

High-Throughput Flexible Constraint Length Viterbi Decoders on De Bruijn, Shuffle-Exchange and Butterfly Connected Architectures

Flexible constraint length channel decoders are required for software defined radios. This paper presents a novel scalable scheme for realizing flexible constraint length Viterbi decoders on a de Bruijn interconnection network. Architectures for flexible decoders using the flattened butterfly and shuffle-exchange networks are also described. It is shown that these networks provide favourable substrates for realizing flexible convolutional decoders. Synthesis results for the three networks are provided and a comparison is performed. An architecture based on a 2D-mesh, which is a topology having a nominally lesser silicon area requirement, is also considered as a fourth point for comparison. It is found that of all the networks considered, the de Bruijn network offers the best tradeoff in terms of area versus throughput.

Parallel and antiparallel aggregation of alpha-helices. Crystal structures of two apolar decapeptides X-Trp-Ile-Ala-Aib-Ile-Val-Aib-Leu-Aib-Pro-OMe (X = Boc, Ac)

An apolar helical decapeptide with different end groups, Boc- or Ac-, crystallizes in a completely parallel fashion for the Boc-analog and in an antiparallel fashion for the Ac-analog. In both crystals, the packing motif consists of rows of parallel molecules. In the Boc-crystals, adjacent rows assemble with the helix axes pointed in the same direction. In the Ac-crystals, adjacent rows assemble with the helix axes pointed in opposite directions. The conformations of the molecules in both crystals are quite similar, predominantly alpha-helical, except for the tryptophanyl side chain where chi 1 congruent to 60 degrees in the Boc- analog and congruent to 180 degrees in the Ac-analog. As a result, there is one lateral hydrogen bond between helices, N(1 epsilon)...O(7), in the Ac-analog. The structures do not provide a ready rationalization of packing preference in terms of side-chain interactions and do not support a major role for helix dipole interactions in determining helix orientation in crystals. The crystal parameters are as follow. Boc-analog: C60H97N11O13.C3H7OH, space group Pl with a = 10.250(3) A, b = 12.451(4) A, c = 15.077(6) A, alpha = 96.55(3) degrees, beta = 92.31(3) degrees, gamma = 106.37(3) degrees, Z = 1, R = 5.5% for 5581 data ([F] greater than 3.0 sigma(F)), resolution 0.89 A. Ac-analog: C57H91N11O12, space group P2(1) with a = 9.965(1) A, b = 19.707(3) A, c = 16.648(3) A, beta = 94.08(1), Z = 2, R = 7.2% for 2530 data ([F] greater than 3.0 sigma(F)), resolution 1.00 A.

BER-optimized linear parallel interference cancellers for multicarrier DS-CDMA systems

In this paper, we consider the design and bit-error performance analysis of linear parallel interference cancellers (LPIC) for multicarrier (MC) direct-sequence code division multiple access (DS-CDMA) systems. We propose an LPIC scheme where we estimate and cancel the multiple access interference (MAT) based on the soft decision outputs on individual subcarriers, and the interference cancelled outputs on different subcarriers are combined to form the final decision statistic. We scale the MAI estimate on individual subcarriers by a weight before cancellation. In order to choose these weights optimally, we derive exact closed-form expressions for the bit-error rate (BER) at the output of different stages of the LPIC, which we minimize to obtain the optimum weights for the different stages. In addition, using an alternate approach involving the characteristic function of the decision variable, we derive BER expressions for the weighted LPIC scheme, matched filter (MF) detector, decorrelating detector, and minimum mean square error (MMSE) detector for the considered multicarrier DS-CDMA system. We show that the proposed BER-optimized weighted LPIC scheme performs better than the MF detector and the conventional LPIC scheme (where the weights are taken to be unity), and close to the decorrelating and MMSE detectors.

Free convection heat transfer between vertical parallel plates

A new mathematical model for the solution of the problem of free convection heat transfer between vertical parallel flat isothermal plates under isothermal boundary conditions, has been presented. The set of boundary layer equations used in the model are transformed to nonlinear coupled differential equations by similarity type variables as obtained by Ostrach for vertical flat plates in an infinite fluid medium. By utilising a parameter ηw* to represent the outer boundary, the governing differential equations are solved numerically for parametric values of Pr = 0.733. 2 and 3, and ηw* = 0.1, 0.5, 1, 2, 3, 4, ... and 8.0. The velocity and temperature profiles are presented. Results indicate that ηw* can effectively classify the system into (1) thin layers where conduction predominates, (2) intermediate layers and (3) thick layers whose results can be predicted by the solutions for vertical flat plates in infinite fluid medium. Heat transfer correlations are presented for the 3 categories. Several experimental and analytical results available in the literature agree with the present correlations.

Singularity and controllability analysis of parallel manipulators and closed-loop mechanisms

This paper presents a study of kinematic and force singularities in parallel manipulators and closed-loop mechanisms and their relationship to accessibility and controllability of such manipulators and closed-loop mechanisms, Parallel manipulators and closed-loop mechanisms are classified according to their degrees of freedom, number of output Cartesian variables used to describe their motion and the number of actuated joint inputs. The singularities in the workspace are obtained by considering the force transformation matrix which maps the forces and torques in joint space to output forces and torques ill Cartesian space. The regions in the workspace which violate the small time local controllability (STLC) and small time local accessibility (STLA) condition are obtained by deriving the equations of motion in terms of Cartesian variables and by using techniques from Lie algebra.We show that for fully actuated manipulators when the number ofactuated joint inputs is equal to the number of output Cartesian variables, and the force transformation matrix loses rank, the parallel manipulator does not meet the STLC requirement. For the case where the number of joint inputs is less than the number of output Cartesian variables, if the constraint forces and torques (represented by the Lagrange multipliers) become infinite, the force transformation matrix loses rank. Finally, we show that the singular and non-STLC regions in the workspace of a parallel manipulator and closed-loop mechanism can be reduced by adding redundant joint actuators and links. The results are illustrated with the help of numerical examples where we plot the singular and non-STLC/non-STLA regions of parallel manipulators and closed-loop mechanisms belonging to the above mentioned classes. (C) 2000 Elsevier Science Ltd. All rights reserved.