Additive Spanners and (alpha, beta)-Spanners

An (alpha, beta)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of a and an additive term beta. It is well known that any graph contains a (multiplicative) (2k - 1, 0)-spanner of size O(n(1+1/k)) and an (additive) (1, 2)-spanner of size O(n(3/2)). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (alpha, beta)-spanners. Our first result is an additive (1, 6)-spanner of size O(n(4/3)). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (alpha, beta)-spanners can be computed efficiently, ideally in linear time. We show that, for any k, a (k, k - 1)-spanner with size O(kn(1+1/k)) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

Some results and approaches for reconstruction conjectures

Tutte (1979) proved that the disconnected spanning subgraphs of a graph can be reconstructed from its vertex deck. This result is used to prove that if we can reconstruct a set of connected graphs from the shuffled edge deck (SED) then the vertex reconstruction conjecture is true. It is proved that a set of connected graphs can be reconstructed from the SED when all the graphs in the set are claw-free or all are P-4-free. Such a problem is also solved for a large subclass of the class of chordal graphs. This subclass contains maximal outerplanar graphs. Finally, two new conjectures, which imply the edge reconstruction conjecture, are presented. Conjecture 1 demands a construction of a stronger k-edge hypomorphism (to be defined later) from the edge hypomorphism. It is well known that the Nash-Williams' theorem applies to a variety of structures. To prove Conjecture 2, we need to incorporate more graph theoretic information in the Nash-Williams' theorem.

Squeezed vacuum as an eigenstate of two-photon annihilation operator

We introduce the inverse annihilation and creation operators a-1 and a(dagger-1) by their actions on the number states. We show that the squeezed vacuum exp(1/2xia(dagger2)]\0] and squeezed first number state exp[1.2xia(dagger2)]\n = 1] are respectively the eigenstates of the operators (a(dagger-1)a) and (aa(dagger-1)) with the eigenvalue xi.

Design issues and caching strategies for CD-ROM based multimedia storage

CD-ROMs have proliferated as a distribution media for desktop machines for a large variety of multimedia applications (targeted for a single-user environment) like encyclopedias, magazines and games. With CD-ROM capacities up to 3 GB being available in the near future, they will form an integral part of Video on Demand (VoD) servers to store full-length movies and multimedia. In the first section of this paper we look at issues related to the single- user desktop environment. Since these multimedia applications are highly interactive in nature, we take a pragmatic approach, and have made a detailed study of the multimedia application behavior in terms of the I/O request patterns generated to the CD-ROM subsystem by tracing these patterns. We discuss prefetch buffer design and seek time characteristics in the context of the analysis of these traces. We also propose an adaptive main-memory hosted cache that receives caching hints from the application to reduce the latency when the user moves from one node of the hyper graph to another. In the second section we look at the use of CD-ROM in a VoD server and discuss the problem of scheduling multiple request streams and buffer management in this scenario. We adapt the C-SCAN (Circular SCAN) algorithm to suit the CD-ROM drive characteristics and prove that it is optimal in terms of buffer size management. We provide computationally inexpensive relations by which this algorithm can be implemented. We then propose an admission control algorithm which admits new request streams without disrupting the continuity of playback of the previous request streams. The algorithm also supports operations such as fast forward and replay. Finally, we discuss the problem of optimal placement of MPEG streams on CD-ROMs in the third section.

Automatic identification of modal damping from Floquet analysis

A practical method is proposed to identify the mode associated with the frequency part of the eigenvalue of the Floquet transition matrix (FTM). From the FTM eigenvector, which contains the states and their derivatives, the ratio of the derivative and the state corresponding to the largest component is computed. The method exploits the fact that the imaginary part of this (complex) ratio closely approximates the frequency of the mode. It also lends itself well to automation and has been tested over a large number of FTMs of order as high as 250.

Coherent-mode decomposition of general anisotropic Gaussian Schell-model beams

We present a complete solution to the problem of coherent-mode decomposition of the most general anisotropic Gaussian Schell-model (AGSM) beams, which constitute a ten-parameter family. Our approach is based on symmetry considerations. Concepts and techniques familiar from the context of quantum mechanics in the two-dimensional plane are used to exploit the Sp(4, R) dynamical symmetry underlying the AGSM problem. We take advantage of the fact that the symplectic group of first-order optical system acts unitarily through the metaplectic operators on the Hilbert space of wave amplitudes over the transverse plane, and, using the Iwasawa decomposition for the metaplectic operator and the classic theorem of Williamson on the normal forms of positive definite symmetric matrices under linear canonical transformations, we demonstrate the unitary equivalence of the AGSM problem to a separable problem earlier studied by Li and Wolf [Opt. Lett. 7, 256 (1982)] and Gori and Guattari [Opt. Commun. 48, 7 (1983)]. This conn ction enables one to write down, almost by inspection, the coherent-mode decomposition of the general AGSM beam. A universal feature of the eigenvalue spectrum of the AGSM family is noted.

Stability analysis of stochastically parametered nonconservative columns

Nonconservatively loaded columns. which have stochastically distributed material property values and stochastic loadings in space are considered. Young's modulus and mass density are treated to constitute random fields. The support stiffness coefficient and tip follower load are considered to be random variables. The fluctuations of external and distributed loadings are considered to constitute a random field. The variational formulation is adopted to get the differential equation and boundary conditions. The non self-adjoint operators are used at the boundary of the regularity domain. The statistics of vibration frequencies and modes are obtained using the standard perturbation method, by treating the fluctuations to be stochastic perturbations. Linear dependence of vibration and stability parameters over property value fluctuations and loading fluctuations are assumed. Bounds for the statistics of vibration frequencies are obtained. The critical load is first evaluated for the averaged problem and the corresponding eigenvalue statistics are sought. Then, the frequency equation is employed to transform the eigenvalue statistics to critical load statistics. Specialization of the general procedure to Beck, Leipholz and Pfluger columns is carried out. For Pfluger column, nonlinear transformations are avoided by directly expressing the critical load statistics in terms of input variable statistics.

Stability of stochastic Leipholz column with stochastic loading

The Leipholz column which is having the Young modulus and mass per unit length as stochastic processes and also the distributed tangential follower load behaving stochastically is considered. The non self-adjoint differential equation and boundary conditions are considered to have random field coefficients. The standard perturbation method is employed. The non self-adjoint operators are used within the regularity domain. Full covariance structure of the free vibration eigenvalues and critical loads is derived in terms of second order properties of input random fields characterizing the system parameter fluctuations. The mean value of critical load is calculated using the averaged problem and the corresponding eigenvalue statistics are sought. Through the frequency equation a transformation is done to yield load parameter statistics. A numerical study incorporating commonly observed correlation models is reported which illustrates the full potentials of the derived expressions.

Towards building an intelligent decision support system for project management

Management of large projects, especially the ones in which a major component of R&D is involved and those requiring knowledge from diverse specialised and sophisticated fields, may be classified as semi-structured problems. In these problems, there is some knowledge about the nature of the work involved, but there are also uncertainties associated with emerging technologies. In order to draw up a plan and schedule of activities of such a large and complex project, the project manager is faced with a host of complex decisions that he has to take, such as, when to start an activity, for how long the activity is likely to continue, etc. An Intelligent Decision Support System (IDSS) which aids the manager in decision making and drawing up a feasible schedule of activities while taking into consideration the constraints of resources and time, will have a considerable impact on the efficient management of the project. This report discusses the design of an IDSS that helps in project planning phase through the scheduling phase. The IDSS uses a new project scheduling tool, the Project Influence Graph (PIG).

Chordal Bipartite Graphs with High Boxicity

The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than 4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity.

Enhanced sensitivity for the differential pulse polarographic determination of molybdenum(VI) based on adsorption catalytic current

A differential pulse polarographic (DPP) method based on the adsorption catalytic current in a medium containing chlorate and 8-hydroxyquinoline (oxine) is suggested for the determination of molybdenum(VI). Experimental conditions such as pH and the composition of supporting electrolyte have been optimized to get a linear calibration graph at trace levels of Mo(VI). The sensitivity for molybdenum can be considerably enhanced by this method. The influence of possible interferences on the catalytic current has been investigated. The sensitivity of the method is compared with those obtained for other DPP methods for molybdenum. A detection limit of 1.0 x 10(-8) mol/L has been found.

Network approach for capturing ligand-induced subtle global changes in protein structures

Ligand-induced conformational changes in proteins are of immense functional relevance. It is a major challenge to elucidate the network of amino acids that are responsible for the percolation of ligand-induced conformational changes to distal regions in the protein from a global perspective. Functionally important subtle conformational changes (at the level of side-chain noncovalent interactions) upon ligand binding or as a result of environmental variations are also elusive in conventional studies such as those using root-mean-square deviations (r.m.s.d.s). In this article, the network representation of protein structures and their analyses provides an efficient tool to capture these variations (both drastic and subtle) in atomistic detail in a global milieu. A generalized graph theoretical metric, using network parameters such as cliques and/or communities, is used to determine similarities or differences between structures in a rigorous manner. The ligand-induced global rewiring in the protein structures is also quantified in terms of network parameters. Thus, a judicious use of graph theory in the context of protein structures can provide meaningful insights into global structural reorganizations upon perturbation and can also be helpful for rigorous structural comparison. Data sets for the present study include high-resolution crystal structures of serine proteases from the S1A family and are probed to quantify the ligand-induced subtle structural variations.

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.

Some results on the reconstruction problems. p-claw-free, chordal, and p4-reducible graphs

A claw is an induced subgraph isomorphic to K-1,K-3. The claw-point is the point of degree 3 in a claw. A graph is called p-claw-free when no p-cycle has a claw-point on it. It is proved that for p greater than or equal to 4, p-claw-free graphs containing at least one chordless p-cycle are edge reconstructible. It is also proved that chordal graphs are edge reconstructible. These two results together imply the edge reconstructibility of claw-free graphs. A simple proof of vertex reconstructibility of P-4-reducible graphs is also presented. (C) 1995 John Wiley and Sons, Inc.

Symmetrizing a Hessenberg matrix: Designs for VLSI parallel processor arrays

A symmetrizer of a nonsymmetric matrix A is the symmetric matrix X that satisfies the equation XA = A(t)X, where t indicates the transpose. A symmetrizer is useful in converting a nonsymmetric eigenvalue problem into a symmetric one which is relatively easy to solve and finds applications in stability problems in control theory and in the study of general matrices. Three designs based on VLSI parallel processor arrays are presented to compute a symmetrizer of a lower Hessenberg matrix. Their scope is discussed. The first one is the Leiserson systolic design while the remaining two, viz., the double pipe design and the fitted diagonal design are the derived versions of the first design with improved performance.