Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R-1 x R-2 x ... x R-k where each R-i is a closed interval on the real line. The boxicity of a graph G,denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R-1 x R-2 x ... x R-k where each Ri is a closed interval on the real line of the form [a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G) <= t + inverted right perpendicularlog(n - t)inverted left perpendicular - 1 and box(G) <= left perpendiculart/2right perpendicular + 1, where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, box(G) <= left perpendicularn/2right perpendicular and cub(G) <= inverted right perpendicular2n/3inverted left perpendicular, where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then box(G) <= inverted right perpendicularn/4inverted left perpendicular and this bound is tight. We also show that if G is a bipartite graph then cub(G) <= n/2 + inverted right perpendicularlog n inverted left perpendicular - 1. We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to n/4. Interestingly, if boxicity is very close to n/2, then chromatic number also has to be very high. In particular, we show that if box(G) = n/2 - s, s >= 0, then chi (G) >= n/2s+2, where chi (G) is the chromatic number of G.

Autonomous Line Scanning for SPC Telephone Switching Systems

An Autonomous Line Scanning Unit (ALSU) for completely autonomous detection of call originations in the SPC Telephone Switching System is described. Through its own memories, ALSU maintains an up-to-date record of subscribers' statuses, detects call originations, performs 'hit timing check' and informs the Switching System of the identity of calling subscribers. The ALSU needs minimum interaction with the Central Processor, resulting in increased call handling capacity

Time-Domain Measurement of Voltage Induction by Transient EM Fields

An efficient measurement technique for studying the effect of transient electromagnetic fields under controlled conditions has been described. Broad-band TEM fields with a rise-time of a few nanoseconds were generated using a stripline method. Theoretical results are obtained and experimental measurements which confirm these results are described. The work will form the basis for a study of the susceptibility of digital integrated circuits and their interconnections to transient electromagnetic fields.

Thermodynamic characterization of the reversible, two-state unfolding of maltose binding protein, a large two-domain protein

The folding and stability of maltose binding protein (MBP) have been investigated as a function of pH and temperature by intrinsic tryptophan fluorescence, far- and near-UV circular dichroism, and high-sensitivity differential scanning calorimetric measurements. MBP is a monomeric, two-domain protein containing 370 amino acids. The protein is stable in the pH range of 4-10.5 at 25 degrees C. The protein exhibits reversible, two-state, thermal and guanidine hydrochloride-mediated denaturation at neutral pH. The thermostability of MBP is maximal at pH 6, with a Tm of 64.9 degrees C and a deltaHm of 259.7 kcal mol(-1). The linear dependence of deltaHm on Tm was used to estimate a value of deltaCp of 7.9 kcal mol(-1) K(-1) or 21.3 cal (mol of residue)(-1) K(-1). These values are higher than the corresponding deltaCp's for most globular proteins studied to date. However, the extrapolated values of deltaH and deltaS (per mole of residue) at 110 degrees C are similar to those of other globular proteins. These data have been used to show that the temperature at which a protein undergoes cold denaturation depends primarily on the deltaCp (per mol of residue) and that this temperature increases with an increase in deltaCp. The predicted decrease in stability of MBP at low temperatures was experimentally confirmed by carrying out denaturant-mediated unfolding studies at neutral pH at 2 and 28 degrees C.

A feedback-based algorithm forMotion analysis with application to object tracking

We present a motion detection algorithm which detects direction of motion at sufficient number of points and thus segregates the edge image into clusters of coherently moving points. Unlike most algorithms for motion analysis, we do not estimate magnitude of velocity vectors or obtain dense motion maps. The motivation is that motion direction information at a number of points seems to be sufficient to evoke perception of motion and hence should be useful in many image processing tasks requiring motion analysis. The algorithm essentially updates the motion at previous time using the current image frame as input in a dynamic fashion. One of the novel features of the algorithm is the use of some feedback mechanism for evidence segregation. This kind of motion analysis can identify regions in the image that are moving together coherently, and such information could be sufficient for many applications that utilize motion such as segmentation, compression, and tracking. We present an algorithm for tracking objects using our motion information to demonstrate the potential of this motion detection algorithm.

Evaluation of Moderate-Resolution Imaging Spectroradiometer (MODIS) collection 004 (C004) aerosol retrievals at Kanpur, Indo-Gangetic basin

[1] We have compared the spectral aerosol optical depth (AOD, tau lambda) and aerosol fine mode fraction (AFMF) of Collection 004 (C004) derived from Moderate-Resolution Imaging Spectroradiometer (MODIS) on board National Aeronautics and Space Administration's (NASA) Terra and Aqua platforms with that obtained from Aerosol Robotic Network (AERONET) at Kanpur (26.45 degrees N, 80.35 degrees E), India for the period 2001-2005. The spatially-averaged (0.5 degrees x 0.5 degrees centered at AERONET sunphotometer) MODIS Level-2 aerosol parameters (10 km at nadir) were compared with the temporally averaged AERONET-measured AOD (within +/- 30 minutes of MODIS overpass). We found that MODIS systematically overestimated AOD during the pre-monsoon season (March to June, known to be influenced by dust aerosols). The errors in AOD at 0.66 mu m were correlated with the apparent reflectance at 2.1 mu m (rho*(2.1)) which MODIS C004 uses to estimate the surface reflectance in the visible channels (rho(0.47) = rho*(2.1)/ 4, rho(0.66) = rho*(2.1)/ 2). The large errors in AOD (Delta tau(0.66) > 0.3) are found to be associated with the higher values of rho*(2.1) (0.18 to 0.25), where the uncertainty in the ratios of reflectance is large (Delta rho(0.66) +/- 0.04, Delta rho(0.47) +/- 0.02). This could have resulted in lower surface reflectance, higher aerosol path radiance and thus lead to overestimation in AOD. While MODIS-derived AFMF has binary distribution (1 or 0) with too low (AFMF < 0.2) during dust-loading period, and similar to 1 for the rest of the retrievals, AERONET showed range of values (0.4 to 0.9). The errors in tau(0.66) were also high in the scattering angle range 110 degrees - 140 degrees, where the optical effects of nonspherical dust particles are different from that of spherical particles.

Splitting Algorithms for Fast Relay Selection: Generalizations, Analysis, and a Unified View

Relay selection for cooperative communications promises significant performance improvements, and is, therefore, attracting considerable attention. While several criteria have been proposed for selecting one or more relays, distributed mechanisms that perform the selection have received relatively less attention. In this paper, we develop a novel, yet simple, asymptotic analysis of a splitting-based multiple access selection algorithm to find the single best relay. The analysis leads to simpler and alternate expressions for the average number of slots required to find the best user. By introducing a new contention load' parameter, the analysis shows that the parameter settings used in the existing literature can be improved upon. New and simple bounds are also derived. Furthermore, we propose a new algorithm that addresses the general problem of selecting the best Q >= 1 relays, and analyze and optimize it. Even for a large number of relays, the scalable algorithm selects the best two relays within 4.406 slots and the best three within 6.491 slots, on average. We also propose a new and simple scheme for the practically relevant case of discrete metrics. Altogether, our results develop a unifying perspective about the general problem of distributed selection in cooperative systems and several other multi-node systems.

Fracture behavior of concrete–concrete interface using acoustic emission technique

The fracture behavior of concrete–concrete interface is characterized using acoustic emission (AE). Beams of different sizes having jointed interface between two different strengths of concrete are tested. The results of load, displacement, CMOD, AE-events and AE-energy are analyzed. The width of fracture process zone and damage zone are computed using AE-data and are found to be independent of size. It is observed that, as the difference in compressive strength of concrete on either side of interface increases, the load carrying capacity, number of AE-events, AE-energy, width of fracture process zone and damage zone decreases.

Explicit Construction of Optimal Exact Regenerating Codes for Distributed Storage

Erasure coding techniques are used to increase the reliability of distributed storage systems while minimizing storage overhead. Also of interest is minimization of the bandwidth required to repair the system following a node failure. In a recent paper, Wu et al. characterize the tradeoff between the repair bandwidth and the amount of data stored per node. They also prove the existence of regenerating codes that achieve this tradeoff. In this paper, we introduce Exact Regenerating Codes, which are regenerating codes possessing the additional property of being able to duplicate the data stored at a failed node. Such codes require low processing and communication overheads, making the system practical and easy to maintain. Explicit construction of exact regenerating codes is provided for the minimum bandwidth point on the storage-repair bandwidth tradeoff, relevant to distributed-mail-server applications. A sub-space based approach is provided and shown to yield necessary and sufficient conditions on a linear code to possess the exact regeneration property as well as prove the uniqueness of our construction. Also included in the paper, is an explicit construction of regenerating codes for the minimum storage point for parameters relevant to storage in peer-to-peer systems. This construction supports a variable number of nodes and can handle multiple, simultaneous node failures. All constructions given in the paper are of low complexity, requiring low field size in particular.

Relay Selection and Data Transmission Throughput Tradeoff in Cooperative Systems

A common and practical paradigm in cooperative communications is the use of a dynamically selected 'best' relay to decode and forward information from a source to a destination. Such a system consists of two core phases: a relay selection phase, in which the system expends resources to select the best relay, and a data transmission phase, in which it uses the selected relay to forward data to the destination. In this paper, we study and optimize the trade-off between the selection and data transmission phase durations. We derive closed-form expressions for the overall throughput of a non-adaptive system that includes the selection phase overhead, and then optimize the selection and data transmission phase durations. Corresponding results are also derived for an adaptive system in which the relays can vary their transmission rates. Our results show that the optimal selection phase overhead can be significant even for fast selection algorithms. Furthermore, the optimal selection phase duration depends on the number of relays and whether adaptation is used.

A Low ML-Decoding Complexity, High Coding Gain, Full-Rate, Full-Diversity STBC for 4 x 2 MIMO System

This paper proposes a full-rate, full-diversity space-time block code(STBC) with low maximum likelihood (ML) decoding complexity and high coding gain for the 4 transmit antenna, 2 receive antenna (4 x 2) multiple-input multiple-output (MIMO) system that employs 4/16-QAM. For such a system, the best code known is the DjABBA code and recently, Biglieri, Hong and Viterbo have proposed another STBC (BHV code) for 4-QAM which has lower ML-decoding complexity than the DjABBA code but does not have full-diversity like the DjABBA code. The code proposed in this paper has the same ML-decoding complexity as the BHV code for any square M-QAM but has full-diversity for 4- and 16-QAM. Compared with the DjABBA code, the proposed code has lower ML-decoding complexity for square M-QAM constellation, higher coding gain for 4- and 16-QAM, and hence a better codeword error rate (CER) performance. Simulation results confirming this are presented.

Analysis,Insights and Generalization of a Fast Decentralized Relay Selection Mechanism

Relay selection for cooperative communications has attracted considerable research interest recently. While several criteria have been proposed for selecting one or more relays and analyzed, mechanisms that perform the selection in a distributed manner have received relatively less attention. In this paper, we analyze a splitting algorithm for selecting the single best relay amongst a known number of active nodes in a cooperative network. We develop new and exact asymptotic analysis for computing the average number of slots required to resolve the best relay. We then propose and analyze a new algorithm that addresses the general problem of selecting the best Q >= 1 relays. Regardless of the number of relays, the algorithm selects the best two relays within 4.406 slots and the best three within 6.491 slots, on average. Our analysis also brings out an intimate relationship between multiple access selection and multiple access control algorithms.

Regenerating Codes for Distributed Storage Networks

In a storage system where individual storage nodes are prone to failure, the redundant storage of data in a distributed manner across multiple nodes is a must to ensure reliability. Reed-Solomon codes possess the reconstruction property under which the stored data can be recovered by connecting to any k of the n nodes in the network across which data is dispersed. This property can be shown to lead to vastly improved network reliability over simple replication schemes. Also of interest in such storage systems is the minimization of the repair bandwidth, i.e., the amount of data needed to be downloaded from the network in order to repair a single failed node. Reed-Solomon codes perform poorly here as they require the entire data to be downloaded. Regenerating codes are a new class of codes which minimize the repair bandwidth while retaining the reconstruction property. This paper provides an overview of regenerating codes including a discussion on the explicit construction of optimum codes.

Analysis of edge delaminations in laminates through combined use of quasi-three-dimensional, eight-noded, two-noded and transition elements

The use of appropriate finite elements in different regions of a stressed solid can be expected to be economical in computing its stress response. This concept is exploited here in studying stresses near free edges in laminated coupons. The well known free edge problem of [0/90], symmetric laminate is considered to illustrate the application of the concept. The laminate is modelled as a combination of three distinct regions. Quasi-three-dimensional eight-noded quadrilateral isoparametric elements (Q3D8) are used at and near the free edge of the laminate and two-noded line elements (Q3D2) are used in the region away from the free edge. A transition element (Q3DT) provides a smooth inter-phase zone between the two regions. Significant reduction in the problem size and hence in the computational time and cost have been achieved at almost no loss of accuracy.