Home About us Contact
|
Home About us Contact | ||
|
|
||
Underlying Graph (underlying + graph)
Selected AbstractsThe 2-dimensional rigidity of certain families of graphsJOURNAL OF GRAPH THEORY, Issue 2 2007Bill Jackson Abstract Laman's characterization of minimally rigid 2-dimensional generic frameworks gives a matroid structure on the edge set of the underlying graph, as was first pointed out and exploited by L. Lovász and Y. Yemini. Global rigidity has only recently been characterized by a combination of two results due to T. Jordán and the first named author, and R. Connelly, respectively. We use these characterizations to investigate how graph theoretic properties such as transitivity, connectivity and regularity influence (2-dimensional generic) rigidity and global rigidity and apply some of these results to reveal rigidity properties of random graphs. In particular, we characterize the globally rigid vertex transitive graphs, and show that a random d -regular graph is asymptotically almost surely globally rigid for all d , 4. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 154,166, 2007 [source] Structural learning with time-varying components: tracking the cross-section of financial time seriesJOURNAL OF THE ROYAL STATISTICAL SOCIETY: SERIES B (STATISTICAL METHODOLOGY), Issue 3 2005Makram Talih Summary., When modelling multivariate financial data, the problem of structural learning is compounded by the fact that the covariance structure changes with time. Previous work has focused on modelling those changes by using multivariate stochastic volatility models. We present an alternative to these models that focuses instead on the latent graphical structure that is related to the precision matrix. We develop a graphical model for sequences of Gaussian random vectors when changes in the underlying graph occur at random times, and a new block of data is created with the addition or deletion of an edge. We show how a Bayesian hierarchical model incorporates both the uncertainty about that graph and the time variation thereof. [source] Approximability of unsplittable shortest path routing problems,NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2009Andreas Bley Abstract In this article, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph D = (V,A) and a set K of directed commodities, an USPR is a set of flow paths P, (s,t) , K, such that there exists a metric , = (,a) , Z with respect to which each P is the unique shortest (s,t)-path. In the Min-Con-USPR problem, we seek an USPR that minimizes the maximum congestion over all arcs. We show that this problem is NP-hard to approximate within a factor of O(|V|1,,), but polynomially approximable within min(|A|,|K|) in general and within O(1) if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of ,(|V|2) larger than that achievable by unsplittable flow routing or by shortest multipath routing, and a factor of ,(|V|) larger than that achievable by unsplittable source-invariant routing. In the CAP -USPR problem, we seek a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is NP-hard to approximate within 2 , , even in the undirected case, and we devise approximation algorithms for various special cases. The fixed charge network design problem FC-USPR, where the task is to find a minimum cost subgraph of D whose fixed arc capacities admit an USPR of the commodities, is shown to be NPO-complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi-path routing problems. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009 [source] Rapid mixing of Gibbs sampling on graphs that are sparse on averageRANDOM STRUCTURES AND ALGORITHMS, Issue 2 2009Elchanan Mossel Abstract Gibbs sampling also known as Glauber dynamics is a popular technique for sampling high dimensional distributions defined on graphs. Of special interest is the behavior of Gibbs sampling on the Erd,s-Rényi random graph G(n,d/n), where each edge is chosen independently with probability d/n and d is fixed. While the average degree in G(n,d/n) is d(1 - o(1)), it contains many nodes of degree of order log n/log log n. The existence of nodes of almost logarithmic degrees implies that for many natural distributions defined on G(n,p) such as uniform coloring (with a constant number of colors) or the Ising model at any fixed inverse temperature ,, the mixing time of Gibbs sampling is at least n1+,(1/log log n). Recall that the Ising model with inverse temperature , defined on a graph G = (V,E) is the distribution over {±}Vgiven by . High degree nodes pose a technical challenge in proving polynomial time mixing of the dynamics for many models including the Ising model and coloring. Almost all known sufficient conditions in terms of , or number of colors needed for rapid mixing of Gibbs samplers are stated in terms of the maximum degree of the underlying graph. In this work, we show that for every d < , and the Ising model defined on G (n, d/n), there exists a ,d > 0, such that for all , < ,d with probability going to 1 as n ,,, the mixing time of the dynamics on G (n, d/n) is polynomial in n. Our results are the first polynomial time mixing results proven for a natural model on G (n, d/n) for d > 1 where the parameters of the model do not depend on n. They also provide a rare example where one can prove a polynomial time mixing of Gibbs sampler in a situation where the actual mixing time is slower than npolylog(n). Our proof exploits in novel ways the local tree like structure of Erd,s-Rényi random graphs, comparison and block dynamics arguments and a recent result of Weitz. Our results extend to much more general families of graphs which are sparse in some average sense and to much more general interactions. In particular, they apply to any graph for which every vertex v of the graph has a neighborhood N(v) of radius O(log n) in which the induced sub-graph is a tree union at most O(log n) edges and where for each simple path in N(v) the sum of the vertex degrees along the path is O(log n). Moreover, our result apply also in the case of arbitrary external fields and provide the first FPRAS for sampling the Ising distribution in this case. We finally present a non Markov Chain algorithm for sampling the distribution which is effective for a wider range of parameters. In particular, for G(n, d/n) it applies for all external fields and , < ,d, where d tanh(,d) = 1 is the critical point for decay of correlation for the Ising model on G(n, d/n). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 [source] Minimum spanners of butterfly graphsNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2001Shien-Ching Hwang Abstract Given a connected graph G, a spanning subgraph G, of G is called a t -spanner if every pair of two adjacent vertices in G has a distance of at most t in G,. A t -spanner of a graph G is minimum if it contains minimum number of edges among all t -spanners of G. Finding minimum spanners for general graphs is rather difficult. Most of previous results were obtained for some particular graphs, for example, butterfly graphs, cube-connected cycles, de Bruijn graphs, Kautz graphs, complete bipartite graphs, and permutation graphs. The butterfly graphs were originally introduced as the underlying graphs of FFT networks which can perform the fast Fourier transform (FFT) very efficiently. In this paper, we successfully construct most of the minimum t -spanners for the k -ary r -dimensional butterfly graphs for 2 , t , 6 and t = 8. © 2001 John Wiley & Sons, Inc. [source] | ||||||||||