Laplace eigenvalues and bandwidth-type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min-sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min-sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.     

OPTIMAL LABELLING OF UNIT INTERVAL GRAPHS

This paper shows that, for every unit interval graph, there is a labelling which is simultaneously optimal for the following seven graph labelling problems: bandwidth, cyclic bandwidth, profile, fill-in, cutwidth, modified cutwidth, and bandwidth sum(linear arrangement).     

A simple branching scheme for vertex coloring problems

We present a branching scheme for some vertex coloring problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme.     

图的二维带宽及其Laplacian特征值

图的二维带宽问题是将图G嵌入平面网格图，并使基于该嵌入的函数取得最优值（通常是最小值）。本文研究了图的二维带宽与其Laplacian特征值之间的关系。     

图的循环带宽和

Abstract. Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.     

二维带宽的浓度下界（英）

二维带宽问题是确定图G在平面格子图中的一个嵌入，使最长的边尽可能短.本文研究若干个下界以及它们应用于带宽的估值.所有结果均建立在一种平面组合几何的方法之上.其中的浓度下界改进了文献[3]的结果.     

Bandwidth of bipartite permutation graphs in polynomial time

We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs.     

The Endogenous Analysis of Flows,with Applications to Migrations,Social Mobility and Opinion Shifts

For exponential random graph models, under quite general conditions, it is proved that induced subgraphs on node sets disconnected from the other nodes still have distributions from an exponential random graph model. This can help in the theoretical interpretation of such models. An application is that for saturated snowball samples from a potentially larger graph which is a realization of an exponential random graph model, it is possible to do the analysis of the observed snowball sample within the framework of exponential random graph models without any knowledge of the larger graph.     

Minimal functions on the random graph

We show that there is a system of 14 non-trivial finitary functions on the random graph with the following properties: Any non-trivial function on the random graph generates one of the functions of this system by means of composition with automorphisms and by topological closure, and the system is minimal in the sense that no subset of the system has the same property. The theorem is obtained by proving a Ramsey-type theorem for colorings of tuples in finite powers of the random graph, and by applying this to find regular patterns in the behavior of any function on the random graph. As model-theoretic corollaries of our methods we rederive a theorem of Simon Thomas classifying the first-order closed reducts of the random graph, and prove some refinements of this theorem; also, we obtain a classification of the maximal reducts closed under primitive positive definitions, and prove that all reducts of the random graph are model-complete.     

Topological properties of the one dimensional exponential random geometric graph

In this article we study the one‐dimensional random geometric (random interval) graph when the location of the nodes are independent and exponentially distributed. We derive exact results and limit theorems for the connectivity and other properties associated with this random graph. We show that the asymptotic properties of a graph with a truncated exponential distribution can be obtained using the exponential random geometric graph. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

带宽等于最小度的图的最小边数

本文对带宽等于最小度的图的边数极值问题进行了研究,主要结果如下:对任意给定的正整数n及r(r相似文献   

Continuous-Time Independent Edge-Markovian Random Graph Process

In this paper, the continuous-time independent edge-Markovian random graph process model is constructed. The authors also define the interval isolated nodes of the random graph process, study the distribution sequence of the number of isolated nodes and the probability of having no isolated nodes when the initial distribution of the random graph process is stationary distribution, derive the lower limit of the probability in which two arbitrary nodes are connected and the random graph is also connected, and prove that the random graph is almost everywhere connected when the number of nodes is sufficiently large.     

On the complexity of loading shallow neural networks

We formalize a notion of loading information into connectionist networks that characterizes the training of feed-forward neural networks. This problem is NP-complete, so we look for tractable subcases of the problem by placing constraints on the network architecture. The focus of these constraints is on various families of “shallow” architectures which are defined to have bounded depth and un-bounded width. We introduce a perspective on shallow networks, called the Support Cone Interaction (SCI) graph, which is helpful in distinguishing tractable from intractable subcases: When the SCI graph is a tree or is of limited bandwidth, loading can be accomplished in polynomial time; when its bandwidth is not limited we find the problem NP-complete even if the SCI graph is a simple 2-dimensional planar grid.     

图的扩张与稀疏矩阵计算中的若干优化问题

本文研究从稀疏矩阵计算中提出的若干离散最优化问题,即带宽,树宽,路宽,侧廓,扩充侧廓及填充问题。实际上,它们是一类图扩张问题;这些问题同时来源于各式各样的课题,如图子式理论,VLSI电路设计,互联网络及分子生物学等,本文从图论观点着重讨论两种统一途径：图的标号及图的扩张。     

On the probability of the occurrence of a copy of a fixed graph in a random distance graph

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erd?s and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.     

Subgraphs of Random Match-Graphs

 A simple graph (match-graph) generated by two-cycles of a general model of a random digraph is considered. Based on relations between a special case of such a graph and a classical model of a random graph, some results about the existence and the number of subgraphs of a given type in a random match-graph are presented. Received: December 8, 1997 Final version received: September 16, 1999     

On cross-bandwidth

The notion of cross-bandwidth is introduced, and it is shown that any graph that is suitably contractible to a k-connected graph has cross-bandwidth at least k. The contracted edges must induce in the original graph a subgraph of maximum degree at most one. This is used to resolve a conjecture of Erdös and Chinn on the bandwidth of certain graphs.     

The product representation of a locally dependent random graph

Directed graphs with random black and white colourings of edges such that the colours of edges from different vertices are mutually independent are called locally dependent random graphs. Two random graphs are equivalent if they cannot be distinguished from percolation processes on them if only the vertices are seen. A necessary and sufficient condition is given for when a locally dependent random graph is equivalent to a product random graph; that is one in which the edges can be grouped in such a way that within each group the colours of the edges are equivalent and between groups they are independent. As an application the random graph corresponding to a spatial general epidemic model is considered.     

A strong law of large numbers for random biased connected graphs

We consider a class of random connected graphs with random vertices and random edges in which the randomness of the vertices is determined by a continuous probability distribution and the randomness of the edges is determined by a connection function. We derive a strong law of large numbers on the total lengths of all random edges for a random biased connected graph that is a generalization of a directed k-nearest-neighbor graph.     

Reducing the bandwidth of a sparse matrix with a genetic algorithm

Abstract

The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.