All-Pairs Bottleneck Paths in Vertex Weighted Graphs

Let G=(V,E,w) be a directed graph, where w:V→ℝ is a weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. For two vertices u,v the capacity from u to v, denoted by c(u,v), is the maximum bottleneck weight of a path from u to v. In the All-Pairs Bottleneck Paths (APBP) problem the task is to find the capacities for all ordered pairs of vertices. Our main result is an O(n ^2.575) time algorithm for APBP. The exponent is derived from the exponent of fast matrix multiplication.     

On Weight Distributions of Shifts of Goethals-like Codes

We study weight distributions of shifts of codes from a well-known family: the 3-error-correcting binary nonlinear Goethals-like codes of length n = 2 ^m , where m 6 is even. These codes have covering radius = 6. We know the weight distribution of any shift of weight i = 1, 2, 3, 5, or 6. For a shift of weight 4, the weight distribution is uniquely defined by the number of leaders in this shift, i.e., the number of vectors of weight 4. We also consider the weight distribution of shifts of codes with minimum distance 7 obtained by deleting any one position of a Goethals-like code of length n.     

Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight ω(v). A multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

A General Class of Heuristics for Minimum Weight Perfect Matching and Fast Special Cases with Doubly and Triply Logarithmic Errors

We give a class of heuristic algorithms for minimum weight perfect matching on a complete edge-weighted graph K(V) satisfying the triangle inequality, where V is a set of an even number, n, of vertices. This class is a generalization of the Onethird heuristics, the hypergreedy heuristic, and it possibly employs any given exact or approximate perfect matching algorithm as an auxiliary heuristic to an appropriate subgraph of K(V). In particular, by using the heuristic of Gabow et al. [3] as its auxiliary heuristic, our algorithm can obtain a solution whose weight is at most times the weight of the optimal solution in time, or a solution with an error of in O(n ² ) time. Received July 21, 1994; revised November 28, 1995.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^{1.5k –1.5k} ((n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation.     

A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problem

The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters, thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight), nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can be solved in a multi-hop ad hoc wireless network of n stations in O(k ^1/2log ^1/2 k)+D _b −1+O(log (max (P _i )+log ²max (P _i )) broadcast rounds with high probability, where k is the number of clusters, D _b is the blocking diameter and max (P _i ), 1≤i≤k, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17–28 2007).     

Trimming of Graphs, with Application to Point Labeling

For t>0 and g≥0, a vertex-weighted graph of total weight W is (t,g)-trimmable if it contains a vertex-induced subgraph of total weight at least (1−1/t)W and with no simple path of more than g edges. A family of graphs is trimmable if for every constant t>0, there is a constant g≥0 such that every vertex-weighted graph in the family is (t,g)-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. We also show that every family of directed graphs of bounded layer bandwidth (a less restrictive condition than bounded directed bandwidth) is trimmable. As an application of these results, we derive polynomial-time approximation schemes for various forms of the problem of labeling a subset of given weighted point features with nonoverlapping sliding axes-parallel rectangular labels so as to maximize the total weight of the labeled features, provided that the ratios of label heights or the ratios of label lengths are bounded by a constant. This settles one of the last major open questions in the theory of map labeling.     

Weight Functions and Generalized Hamming Weights of Linear Codes

We prove that the weight function wt: on a set of messages uniquely determines a linear code of dimension k up to equivalence. We propose a natural way to extend the rth generalized Hamming weight, that is, a function on r-subspaces of a code C, to a function on . Using this, we show that, for each linear code C and any integer r ≤ k = dim C, a linear code exists whose weight distribution corresponds to a part of the generalized weight spectrum of C, from the rth weights to the kth. In particular, the minimum distance of this code is proportional to the rth generalized weight of C.__________Translated from Problemy Peredachi Informatsii, No. 2, 2005, pp. 26–41.Original Russian Text Copyright © 2005 by Nogin.Supported in part by the Russian Foundation for Basic Research, project no. 02-01-01041, and INTAS, grant no. 00-738.     

New results for the minimum weight triangulation problem

Given a finite set of points in a plane, a triangulation is a maximal set of nonintersecting line segments connecting the points. The weight of a triangulation is the sum of the Euclidean lengths of its line segments. No polynomial-time algorithm is known to find a triangulation of minimum weight, nor is the minimum weight triangulation problem known to be NP-hard. This paper proposes a new heuristic algorithm that triangulates a set ofn points inO(n ³⁾ time and that never produces a triangulation whose weight is greater than that of a greedy triangulation. The algorithm produces an optimal triangulation if the points are the vertices of a convex polygon. Experimental results indicate that this algorithm rarely produces a nonoptimal triangulation and performs much better than a seemingly similar heuristic of Lingas. In the direction of showing the minimum weight triangulation problem is NP-hard, two generalizations that are quite close to the minimum weight triangulation problem are shown to be NP-hard.This research was done while the second author was with the Department of Computer Science, Virginia Polytechnic Institute and State University.     

Finding better weight functions for generalized Shepard's operator on infinite intervals

In this paper, we investigate the difference of Shepard's generalized operators S _σ from the approximated set of data for various weight functions σ. Bounds are given for the sizes of the ‘bumps’ shown on the graph of S _σ for σ(d)=1/d in dimension N=1, and the best weight function σ for practical use is proposed.     

Empirical mathematics: the first patterson extension of gauss-kronrod rules

The Kronrod extension (KE) of an n-point Gauss integration rule with respect to some weight w is a (2n+l)-point rule of optimal precision which consists of the n Gauss points and n+1 additional distinct real points contained in the integration interval. KE's may or may not exist depending on w and n. For a KE which exists, we define the first Patterson extension (PE) to be a similar optimal extension of the KE. It contains at least 3n+3 points, in which case it is said to be minimal. We give here some experimental results on the computation of PE's and make some conjectures about the existence of minimal and nonminimal PE's when w is a Jacobi weight.     

Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights

As one of the applications of Grover search, an exact quantum algorithm for the symmetric weight decision problem of a Boolean function has been proposed recently. Although the proposed method shows a quadratic speedup over the classical approach, it only applies to the symmetric case of a Boolean function whose weight is one of the pair {0 < w ₁ < w ₂ < 1, w ₁ + w ₂ = 1}. In this article, we generalize this algorithm in two ways. Firstly, we propose a quantum algorithm for the more general asymmetric case where {0 < w ₁ < w ₂ < 1}. This algorithm is exact and computationally optimal. Secondly, we build on this to exactly solve the multiple weight decision problem for a Boolean function whose weight as one of {0 < w ₁ < w ₂ < · · · < w _m  < 1}. This extended algorithm continues to show a quantum advantage over classical methods. Thirdly, we compare the proposed algorithm with the quantum counting method. For the case with two weights, the proposed algorithm shows slightly lower complexity. For the multiple weight case, the two approaches show different performance depending on the number of weights and the number of solutions. For smaller number of weights and larger number of solutions, the weight decision algorithm can show better performance than the quantum counting method. Finally, we discuss the relationship between the weight decision problem and the quantum state discrimination problem.     

Maximumk-covering of weighted transitive graphs with applications

Consider a weighted transitive graph, where each vertex is assigned a positive weight. Given a positive integerk, the maximumk-covering problem is to findk disjoint cliques covering a set of vertices with maximum total weight. An 0(kn ²)-time algorithm to solve the problem in a transitive graph is proposed, wheren is the number of vertices. Based on the proposed algorithm the weighted version of a number of problems in VLSI layout (e.g.,k-layer topological via minimization), computational geometry (e.g., maximum multidimensionalk-chain), graph theory (e.g., maximumk-independent set in interval graphs), and sequence manipulation (e.g., maximum increasingk-subsequence) can be solved inO(kn ²), wheren is the input size.This Work was supported in part by the National Science Foundation under Grant MIP-8709074 and MIP-8921540.     

The expected additive weight of trees

Summary We consider a general additive weight of random trees which depends on the structure of the subtrees, on weight functions defined on the number of internal and external nodes and on the degrees of the nodes appearing in the tree and its subtrees. Choosing particular weight functions, the corresponding weight is an important parameter appearing in the analysis of sorting and searching algorithms. For a simply generated family of rooted planar trees , we shall derive a general approach to the computation of the average weight of a tree T with n nodes and m leaves for arbitrary weight functions. This general result implies exact and asymptotic expressions for many types of average weights of a tree T with n nodes if the weight functions are arbitrary polynomials in the number of nodes and leaves with coefficients depending on the node degrees.     

Randomized Weighted Caching with Two Page Weights

Abstract. We consider a special case of the weighted caching problem where the weight of every page is either 1 or some fixed number M > 1 . We present a randomized algorithm which achieves a competitive ratio which is O( log k) where k is the number of pages which can fit in the cache.     

Multicolorings of Series-Parallel Graphs

Let G be a graph, and let each vertex v of G have a positive integer weight (v). A multicoloring of G is to assign each vertex v a set of (v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.     

Some new optimal quaternary constant weight codes

Constant weight codes (CWCs) are an important class of codes in coding theory. Generalized Steiner systems GS (2, k, v, g) were first introduced by Etzion and used to construct optimal nonlinear CWCs over an alphabet of size g + 1 with minimum Hamming distance 2k − 3, in which each codeword has length v and weight k. In this paper, Weil’s theorem on character sum estimates is used to show that there exists a GS(2, 4, v, 3) for any prime v ≡ 1 (mod 4) and v > 13. From the coding theory point of view, an optimal nonlinear quaternary (v, 5, 4) CWC exists for such a prime v.     

Polynomial Time Algorithms for 2-Edge-Connectivity Augmentation Problems

Abstract. Given a 2-edge-connected, real weighted graph G with n vertices and m edges, the 2-edge-connectivity augmentation problem is that of finding a minimum weight set of edges of G to be added to a spanning subgraph H of G to make it 2-edge-connected. While the general problem is NP-hard and 2 -approximable, in this paper we prove that it becomes polynomial time solvable if H is a depth-first search tree of G . More precisely, we provide an efficient algorithm for solving this special case which runs in O (M · α(M,n)) time, where α is the classic inverse of Ackermann's function and M=m · α(m,n) . This algorithm has two main consequences: first, it provides a faster 2 -approximation algorithm for the general 2 -edge-connectivity augmentation problem; second, it solves in O (m · α(m,n)) time the problem of restoring, by means of a minimum weight set of replacement edges, the 2 -edge-connectivity of a 2-edge-connected communication network undergoing a link failure.     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Finding least-weight subsequences with fewer processors

By restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takesO(log² n) time on a CREW PRAM with n³/logn processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log² n log logn) time withn/log logn processors, or in O(log² n) time withn logn processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12].