We discuss several parametrizations of the space of circular planar electrical networks. With any circular planar network we associate a canonical minimal network with the same response matrix, called a “standard” network. The conductances of edges in a standard network can be computed as a biratio of Pfaffians constructed from the response matrix. The conductances serve as coordinates that are compatible with the cell structure of circular planar networks in the sense that one conductance degenerates to $0$ or $\infty$ when moving from a cell to a boundary cell. We also show how to test if a network with $n$ nodes is well-connected by checking that $\binom{n}{2}$ minors of the $n\times n$ response matrix are positive; Colin de Verdière had previously shown that it was sufficient to check the positivity of exponentially many minors. For standard networks with $m$ edges, positivity of the conductances can be tested by checking the positivity of $m+1$ Pfaffians.

We describe a new forward-backward variant of Dijkstra's and Spira's single-source shortest paths (SSSP) algorithms. While essentially all SSSP algorithms scan edges only forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with independent exponential edge weights is $O(n)$ with very high probability. This improves on the previous best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is $O(n^2)$, matching a recent algorithm of Demetrescu and Italiano as analyzed by Peres et al. [J. ACM, 60 (2013), 26]. Furthermore, the probability that the new algorithm requires more than $O(n^2)$ time is exponentially small, improving on the $O(n^{-1/26})$ probability bound obtained by Peres et al.

We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the out-going adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on n vertices with independent exponential edge weights is O(n), with very high probability. This improves on the previously best result of O(n log n), which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is O(n2), matching a recent result of Peres et al. Furthermore, the probability that the new algorithm requires more than O(n2) time is exponentially small, improving on the polynomially small probability of Peres et al.

A Boolean function of n bits is balanced if it takes the value 1 with probability 1⁄2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than Θ(n-1/2√ log n). We construct a balanced monotone Boolean function and a randomized algorithm computing it for which each bit is read with probability Θ(n-1⁄3 log n). We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least Θ(n-1𔊪). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n-1𔊫).

Physical mapping is a fundamental component of the human genome project.A physical map consists of a set of probes which mark unique positions on a long fragment of DNA, together with the relative order of the probes on the DNA.This order is inferred from clone-probe hybridization experiments, which determine the probes contained within various fragments of the genome.In practice, the order of the probes is not completely determined by the hybridization experiments.To better design these experiments, researchers have analyzed the expected distribution of "islands" -groups of probes which are known to be near one another-that would result from hybridization experiments with different numbers of clones and probes.In this paper we analyze the distribution of "runs" -groups of probes whose relative order is completely determined by the hybridization experiment.We include analytic, numerical, Monte Carlo, and simulation results on runs, which can further assist in the design of these experiments.

This paper gives a new algorithm for generating random spanning trees. It too is simple, easy to code up, and has nice proofs. The new algorithm also has the following advantages:

Article Embedding leveled hypercube algorithms into hypercubes (extended abstract) Share on Author: David Bruce Wilson View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 264–270https://doi.org/10.1145/140901.141881Online:01 June 1992Publication History 0citation196DownloadsMetricsTotal Citations0Total Downloads196Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access