A square symmetric matrix is a Robinson similarity matrix if entries in its rows and columns are nondecreasing when moving toward the diagonal. A Robinson similarity matrix can be viewed as the affinity matrix between objects arranged in linear order, where objects closer together have higher affinity. We define a new parameter, $\Gamma_{1}$, which measures how badly a given matrix fails to be Robinson similarity. Namely, a matrix is Robinson similarity precisely when its $\Gamma_{1}$ attains zero, and a matrix with small $\Gamma_{1}$ is close (in the normalized $\ell^1$-norm) to a Robinson similarity matrix. Moreover, both $\Gamma_{1}$ and the Robinson similarity approximation can be computed in polynomial time. Thus, our parameter recognizes Robinson similarity matrices which are perturbed by noise and can therefore be a useful tool in the problem of seriation of noisy data.

Rumor spreading is a protocol for modeling the spread of information through a network via user-to-user interaction. The spatial preferred attachment (SPA) model is a random graph model for complex networks: Vertices are placed in a metric space, and the link probability depends on the metric distance between vertices and on their degree. We show that the SPA model typically produces graphs that have small effective diameter, i.e., $O(\log^2 n)$, while rumor spreading is relatively slow, namely, polynomial in $n$.

We investigate the degree distribution resulting from graph generation models based on rank-based attachment. In rank-based attachment, all vertices are ranked according to a ranking scheme. The link probability of a given vertex is proportional to its rank raised to the power $-\alpha$, for some $\alpha\in(0,1)$. Through a rigorous analysis, we show that rank-based attachment models lead to graphs with a power law degree distribution with exponent $1+1/\alpha$ whenever vertices are ranked according to their degree, their age, or a randomly chosen fitness value. We also investigate the case where the ranking is based on the initial rank of each vertex; the rank of existing vertices changes only to accommodate the new vertex. Here, we obtain a sharp threshold for power law behavior. Only if initial ranks are biased towards lower ranks, or chosen uniformly at random, do we obtain a power law degree distribution with exponent $1+1/\alpha$. This indicates that the power law degree distribution often observed in nature can be explained by a rank-based attachment scheme, based on a ranking scheme that can be derived from a number of different factors; the exponent of the power law can be seen as a measure of the strength of the attachment.

A method to generate lower bounds for the channel assignment problem is given. The method is based on the reduction of the channel assignment problem to a problem of covering the demand in a cellular network by preassigned blocks of cells called tiles. This tile cover approach is applied to networks with a cosite constraint and two different constraints between cells. A complete family of lower bounds is obtained, which include a number of new bounds that improve or include almost all known clique bounds. When applied to an example from the literature, the new bounds give better results.

A focused crawler is designed to traverse the Web to gather documents on a specific topic. It is not an easy task to predict which links lead to good pages. In this paper, we present a new approach for prediction of the important links to relevant pages based on a learned user model. In particular, we first collect pages that a user visits during a learning session, where the user browses the Web and specifically marks which pages she is interested in. We then examine the semantic content of these pages to construct a concept graph, which is used to learn the dominant content and link structure leading to target pages using a Hidden Markov Model (HMM). Experiments show that with learned HMM from a user's browsing, the crawling performs better than Best-First strategy.

A k-stable set in a graph is a stable set of size at most k. We study the convex hull of the k-stable sets of a graph, aiming for a complete inequality description. We also consider colorings of weighted graphs by k-stable sets, aiming for a relation between the values of an optimal coloring and an optimal fractional coloring. Results for k=2 and k=3 as well as a number of general conjectures linking fractional and integral colorings are given.

A key to spectrum efficiency is the channel assignment problem (CAP), where frequency channels must be assigned to transmitters while minimizing bandwidth and keeping interference at acceptable levels. A method for obtaining lower bounds for the CAP is presented, which is based on representation of channel assignment as a tour through the network. It is shown how bounds can be generated in a systematic way using polyhedral theory, or obtained computationally using linear programming. Bounds and applications of these bounds to a number of specific instances are given as examples.

For a number of binary cyclic codes with e>e/sub BCH/, algebraic algorithms are given to find the error locator polynomial. Thus, for these codes more errors can be corrected algebraically than by the Berlekamp-Massey algorithm. In some cases, all error patterns of weight up to e can be decoded; in other cases, only error patterns of weight up to e' with e/sub BCH/>