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

Multi-dimensional Goodness-of-Fit Tests for Spectrum Sensing Based on Stochastic Distances

In this paper, we study two multi-dimensional Goodness-of-Fit tests for spectrum sensing in cognitive radios. The multi-dimensional scenario refers to multiple CR nodes, each with multiple antennas, that record multiple observations from multiple primary users for spectrum sensing. These tests, viz., the Interpoint Distance (ID) based test and the h, f distance based tests are constructed based on the properties of stochastic distances. The ID test is studied in detail for a single CR node case, and a possible extension to handle multiple nodes is discussed. On the other hand, the h, f test is applicable in a multi-node setup. A robustness feature of the KL distance based test is discussed, which has connections with Middleton's class A model. Through Monte-Carlo simulations, the proposed tests are shown to outperform the existing techniques such as the eigenvalue ratio based test, John's test, and the sphericity test, in several scenarios.

Studies of the representation of interatomic distances in molecules and crystal as sum of atomic radii

The electron diffraction investigation of the following compounds has been carried out: sulfur, sulfur nitride, realgar, arsenic trisulfide, spiropentane, dimethyltrisulfide, cis and trans lewisite, methylal, and ethylene glycol.

The crystal structures of the following salts have been determined by x-ray diffraction: silver molybdateand hydrazinium dichloride.

Suggested revisions of the covalent radii for B, Si, P, Ge, As, Sn, Sb, and Pb have been made, and values for the covalent radii of Al, Ga, In, Ti, and Bi have been proposed.

The Schomaker-Stevenson revision of the additivity rule for single covalent bond distances has been used in conjunction with the revised radii. Agreement with experiment is in general better with the revised radii than with the former radii and additivity.

The principle of ionic bond character in addition to that present in a normal covalent bond has been applied to the observed structures of numerous molecules. It leads to a method of interpretation which is at least as consistent as the theory of multiple bond formation.

The revision of the additivity rule has been extended to double bonds. An encouraging beginning along these lines has been made, but additional experimental data are needed for clarification.

Microsatellite-centromere distances and microsatellite diversity in different ploidy classes of Chinese shrimp (Fenneropenaeus Chinensis)

This is the first report of microsatellite-centromere mapping in this commercial species Fenneropenaeus Chinensis, and will be important for providing fixed points in the linkage groups of genetic maps. Triploid Chinese shrimp was induced by heat shock. The fertilized eggs were treated either by retention of the first polar body or the second polar body to produce Meiosis I (MI) or Meiosis II (MII) triploid. The triploidy status in each Chinese shrimp could be confirmed by nine polymorphic microsatellite loci, in which the parents with different alleles and the female parents were each heterozygous. The nine loci were mapped in relation to their centromeres in three MII triploid families, which were induced by retention of the second polar bodies after fertilization with sperm. Microsatellite-centromere (M-C) distances ranged from 9.6 cM to 37 cM under the assumption of complete interference. Information on the positions of centromeres in relation to the microsatellite loci will represent a contribution towards assembly of genetic maps in F. chinensis. Twelve polymorphic microsatellites were used to assess the heterozygosity and allelic diversity in different ploidy classes. As expected, triploids were significantly more polymorphic than diploids. The diploids had an average heterozygosity and allelic diversity value of 0.86, whereas the triploids heterozygosity averaged 0.93 and had allelic diversity value of 1.29. However, MI triploids were not significantly more polymorphic than MII in the microsatellite loci.

Indexing Distances in Large Graphs and Applications in Search Tasks

This thesis elaborates on the problem of preprocessing a large graph so that single-pair shortest-path queries can be answered quickly at runtime. Computing shortest paths is a well studied problem, but exact algorithms do not scale well to real-world huge graphs in applications that require very short response time. The focus is on approximate methods for distance estimation, in particular in landmarks-based distance indexing. This approach involves choosing some nodes as landmarks and computing (offline), for each node in the graph its embedding, i.e., the vector of its distances from all the landmarks. At runtime, when the distance between a pair of nodes is queried, it can be quickly estimated by combining the embeddings of the two nodes. Choosing optimal landmarks is shown to be hard and thus heuristic solutions are employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the techniques presented in this thesis is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach which considers selecting landmarks at random. Finally, they are applied in two important problems arising naturally in large-scale graphs, namely social search and community detection.

Experimental study and theoretical analysis of signage legibility distances as a function of observation angle

Signage systems are widely used in buildings to provide information for wayfinding, thereby assisting in navigation during normal circulation of pedestrians and, more importantly, exiting information during emergencies. An important consideration in determining the effectiveness of signs is establishing the region from which the sign is visible to occupants, the so-called Visibility Catchment Area (VCA). This paper attempts to factor into the determination of the VCA of signs, the observation angle of the observer using both experimental and theoretical analysis.