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

Bi-directional Switch Commutation for a Resonant Matrix Converter supplying a Contactless Energy Transmission System

This paper describes a bi-directional switch commutation strategy for a resonant matrix converter loaded with a contactless energy transmission system. Due to the different application compared to classical 3 phase to 3 phase matrix converters supplying induction machines a new investigation of possible commutation principles is necessary. The paper therefore compares the full bridge series-resonant converter with the 3 phase to 2 phase matrix converter. From the commutation of the full bridge series-resonant converter, conditions for the bi-directional switch commutation are derived. One of the main benefits of the derived strategy is the minimization of commutation steps, which is independent from the load current sign.

Multi-point sensing system for plantar pressure measurement

In this paper, the development of a novel multipoint pressure sensor system suitable for the measurement of human foot pressure distribution has been presented. It essentially consists of a matrix of cantilever sensing elements supported by beams. Foil type strain gauges have been employed for the conversion of foot pressure in to proportional electrical response. Information on the signal conditioning circuitry used is given. Also, the results obtained on the performance of the system are included.

Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n = d + 1. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d >= 2k - 2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n = d + 1, k, d >= 2k - 1].

Symmetry of one-dimensional dynamical systems in terms of transfer matrix parameters

The concept of symmetry for passive, one-dimensional dynamical systems is well understood in terms of the impedance matrix, or alternatively, the mobility matrix. In the past two decades, however, it has been established that the transfer matrix method is ideally suited for the analysis and synthesis of such systems. In this paper an investigatiob is described of what symmetry means in terms of the transfer matrix parameters of an passive element or a set of elements. One-dimensional flexural systems with 4 × 4 transfer matrices as well as acoustical and mechanical systems characterized by 2 × 2 transfer matrices are considered. It is shown that the transfer matrix of a symmetrical system, defined with respect to symmetrically oriented state variables, is involutory, and that a physically symmetrical system may not necessarily be functionally or dynamically symmetrical.

Transfer matrix modeling of hyperbolic and parabolic ducts with incompressible mean flow

A general differential equation for the propagation of sound in a variable area duct or nozzle carrying incompressible mean flow (of low Mach number) is derived and solved for hyperbolic and parabolic shapes. Expressions for the state variables of acoustic pressure and acoustic mass velocity of the shapes are derived. Self‐consistent expressions for the four‐pole parameters are developed. The conical, exponential, catenoidal, sine, and cosine ducts are shown to be special cases of hyperbolic ducts. Finally, it is shown that if the mean flow in computing the transmission loss of the mufflers involving hyperbolic and parabolic shapes was not neglected, little practical benefit would be derived.

Formulas for algorithmic computation of impedance matrix using general circuit constants

A set of formulas is derived from general circuit constants which facilitates formation of the impedance matrix of a power system by the bus-impedance method. The errors associated with the lumpedparameter representation of a transmission line are thereby eliminated. The formulas are valid for short lines also, if the relevant general circuit constants are employed. The mutual impedance between the added line and the existing system is not considered, but the approach suggested can well be extended to it.

Matrix Processors Using p-adic Arithmetic for Exact Linear Computations

A unique code (called Hensel's code) is derived for a rational number by truncating its infinite p-adic expansion. The four basic arithmetic algorithms for these codes are described and their application to rational matrix computations is demonstrated by solving a system of linear equations exactly, using the Gaussian elimination procedure.

Interaction of G-Quadruplexes with Nonintercalating Duplex-DNA Minor Groove Binding Ligands

The enzyme telomerase synthesizes the G-rich DNA strands of the telomere and its activity is often associated with cancer. The telomerase may be therefore responsible for the ability of a cancer cell-to escape apoptosis. The G-rich DNA sequences often adopt tetra-stranded structure, known as the G-quadruplex DNA (G4-DNA). The stabilization of the telomeric DNA into the G4-DNA structures by small molecules has been the focus of many researchers for the design and development of new anticancer agents. The compounds which stabilize the G-quadruplex in the telomere inhibit the telomerase activity. Besides telomeres, the G4-DNA forming sequences are present in the genomic regions of biological significance including the transcriptional regulatory and promoter regions of several oncogenes. Inducing a G-quadruplex structure within the G-rich promoter sequences is a potential way of achieving selective gene regulation. Several G-quadruplex stabilizing ligands are known. Minor groove binding ligands (MGBLs) interact with the double-helical DNA through the minor grooves sequence-specifically and interfere with several DNA associated processes. These MGBLs when suitably modified switch their preference sometimes from the duplex DNA to G4-DNA and stabilize the G4-DNA as well. Herein, we focus on the recent advances in understanding the G-quadruplex structures, particularly made by the human telomeric ends, and review the results of various investigations of the interaction of designed organic ligands with the G-quadruplex DNA while highlighting the importance of MGBL-G-quadruplex interactions.

Relaxation: Application to the matrix reconstruction problem

This report describes some preliminary experiments on the use of the relaxation technique for the reconstruction of the elements of a matrix given their various directional sums (or projections).