Weighted parameters in graphs

We use the modular decomposition to give O(n(m + n) algorithms for finding a maximum weighted clique (respectively stable set) and an approximate weighted colouring (respectively partition into cliques) in a graph. As a by-product, we obtain an O(m + n) algorithm for finding a minimum weighted transversal of the C₅ in a graph.     

On the Laplacian spectral radius of weighted trees with a positive weight set

The spectrum of weighted graphs is often used to solve the problems in the design of networks and electronic circuits. We first give some perturbational results on the (signless) Laplacian spectral radius of weighted graphs when some weights of edges are modified; we then determine the weighted tree with the largest Laplacian spectral radius in the set of all weighted trees with a fixed number of pendant vertices and a positive weight set. Furthermore, we also derive the weighted trees with the largest Laplacian spectral radius in the set of all weighted trees with a fixed positive weight set and independence number, matching number or total independence number.     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

A note on weighted minimal cost flows

The minimal ratio problem which is treated in the literature for shortest paths [Dantzig/Blattner/Rao;Karp;Lawler, 1966, 1972] and for spanning trees [Chandrasekaran] is considered in a generalized form for network flow problems. The resulting problem of finding a so-calledweighted minimal cost flow can be solved by a negative circuit algorithm or by a shortest augmenting circuit algorithm. The validity of both algorithms follows from a negative circuit theorem which can be proved for weighted minimal cost flows.     

An efficient solver for weighted Max-SAT

We present a new branch and bound algorithm for weighted Max-SAT, called Lazy which incorporates original data structures and inference rules, as well as a lower bound of better quality. We provide experimental evidence that our solver is very competitive and outperforms some of the best performing Max-SAT and weighted Max-SAT solvers on a wide range of instances.     

Maximum weight independent set in trees

Computing a maximum independent set, weighted or unweighted, isNP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum weight independent set in trees. A divide and conquer approach based on centroid decomposition of trees is used to compute a maximum weight independent set withinO(n logn) time, wheren is the number of vertices in the tree. We introduce a notion of analternating tree which is crucial in obtaining a new independent set from the previous one.     

Weighted Positivity of Second Order Elliptic Systems

Integral inequalities that concern the weighted positivity of a differential operator have important applications in qualitative theory of elliptic boundary value problems. Despite the power of these inequalities, however, it is far from clear which operators have this property. In this paper, we study weighted integral inequalities for general second order elliptic systems in ℝ ⁿ (n ≥ 3) and prove that, with a weight, smooth and positive homogeneous of order 2–n, the system is weighted positive only if the weight is the fundamental matrix of the system, possibly multiplied by a semi-positive definite constant matrix.      

The Cauchy Integral Operator on Weighted Hardy Space

The authors show that the Cauchy integral operator is bounded from Hωp(R1) to hωp(R1) (the weighted local Hardy space). To prove the results, a kind of generalized atoms is introduced and a variant of weighted "Tb theorem" is considered.     

Global Well-Posedness for Higher-Order Schrödinger Equations in Weighted L2 Spaces

We obtain the global well-posedness for Schrödinger equations of higher orders in weighted L² spaces. This is based on weighted L² Strichartz estimates for the corresponding propagator with higher-order dispersion. Our method is also applied to the Airy equation which is the linear component of Korteweg-de Vries type equations.     

Function Spaces with Exponential Weights I

In this paper we define weighted function spaces of type B^s_pq(u) and F^s_pq(u) on the Euclidean space IRⁿ, where u is a weight function of at most exponential growth. In particular, u(x) = exp(±|χ|) is an admissible weight. We prove some basic properties of these spaces, such as completeness and density of the smooth functions.     

Weighted bootstrap for U-statistics

In this paper we investigate the weighted bootstrap for U-statistics and its properties. Under very general choices of random weights and certain regularity conditions, we show that the weighted bootstrap method with U-statistics provides second-order accurate approximations to the distribution of U-statistics. We shall prove this via one-term Edgeworth expansions of weighted U-statistics.     

A novel clustering approach and prediction of optimal number of clusters: global optimum search with enhanced positioning

Cluster analysis of genome-wide expression data from DNA microarray hybridization studies is a useful tool for identifying biologically relevant gene groupings (DeRisi et al. 1997; Weiler et al. 1997). It is hence important to apply a rigorous yet intuitive clustering algorithm to uncover these genomic relationships. In this study, we describe a novel clustering algorithm framework based on a variant of the Generalized Benders Decomposition, denoted as the Global Optimum Search (Floudas et al. 1989; Floudas 1995), which includes a procedure to determine the optimal number of clusters to be used. The approach involves a pre-clustering of data points to define an initial number of clusters and the iterative solution of a Linear Programming problem (the primal problem) and a Mixed-Integer Linear Programming problem (the master problem), that are derived from a Mixed Integer Nonlinear Programming problem formulation. Badly placed data points are removed to form new clusters, thus ensuring tight groupings amongst the data points and incrementing the number of clusters until the optimum number is reached. We apply the proposed clustering algorithm to experimental DNA microarray data centered on the Ras signaling pathway in the yeast Saccharomyces cerevisiae and compare the results to that obtained with some commonly used clustering algorithms. Our algorithm compares favorably against these algorithms in the aspects of intra-cluster similarity and inter-cluster dissimilarity, often considered two key tenets of clustering. Furthermore, our algorithm can predict the optimal number of clusters, and the biological coherence of the predicted clusters is analyzed through gene ontology.     

Weighted Composition Operators Between Weighted Bloch Type Spaces and Weighted Banach Spaces of Holomorphic Functions

Let φ: 𝔻 → 𝔻 and ψ: 𝔻 → ? be analytic maps. They induce a weighted composition operator ψ C _φ acting between weighted Bloch type spaces and weighted Banach spaces of holomorphic functions. Under some assumptions on the weights, we give a necessary as well as a sufficient condition when such an operator is bounded resp. compact.     

Weighted median algorithms for L1 approximation

The weighted median problem arises as a subproblem in certain multivariate optimization problems, includingL ₁ approximation. Three algorithms for the weighted median problem are presented and the relationships between them are discussed. We report on computational experience with these algorithms and on their use in the context of multivariateL ₁ approximation.This work was supported in part by National Science Foundation Grant CCR-8713893 and in part by a grant from The City University of New York PSC-CUNY Research Award program.     

On Rotations and the Generation of Binary Trees

The rotation graph, G_n, has vertex set consisting of all binary trees with n nodes. Two vertices are connected by an edge if a single rotation will transform one tree into the other. We provide a simpler proof of a result of Lucas that G_n, contains a Hamilton path. Our proof deals directly with the pointer representation of the binary tree. This proof provides the basis of an algorithm for generating all binary trees that can be implemented to run on a pointer machine and to use only constant time between the output of successive trees. Ranking and unranking algorithms are developed for the ordering of binary trees implied by the generation algorithm. These algorithms have time complexity O(n²) (arithmetic operations). We also show strong relationships amongst various representations of binary trees and amongst binary tree generation algorithms that have recently appeared in the literature.     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings

A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure has only been concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled with the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to this generality, this algorithm is faster than the previous algorithms.Another contribution of this paper is on maximum weight bipartite matchings. We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced. Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm.     

Weighted Polynomial Approximation in the Complex Plane

Given a pair (G,W) of an open bounded set G in the complex plane and a weight function W(z) which is analytic and different from zero in G , we consider the problem of the locally uniform approximation of any function f(z) , which is analytic in G , by weighted polynomials of the form {W ⁿ (z)P _n (z) } ^$\infinity$ _n=0 , where deg P_n n. The main result of this paper is a necessary and sufficient condition for such an approximation to be valid. We also consider a number of applications of this result to various classical weights, which give explicit criteria for these weighted approximations. May 1, 1996. Date revised: October 8, 1996.     

A Fan Type Condition For Heavy Cycles in Weighted Graphs

 A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree d ^w (v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. max{d ^w (x),d ^w (y)∣d(x,y)=2}≥c/2; 2. w(x z)=w(y z) for every vertex z∈N(x)∩N(y) with d(x,y)=2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least c. This generalizes a theorem of Fan on the existence of long cycles in unweighted graphs to weighted graphs. We also show we cannot omit Condition 2 or 3 in the above result. Received: February 7, 2000 Final version received: June 5, 2001     

A short note on weighted mean matrices

In the present paper we have established a relation between (N, p _n ) and (N, q _n ) weighted mean matrices, when considered as bounded operators on 1^p, 1 < p < ∞.