Random Walks,Bisections and Gossiping in Circulant Graphs

Circulant graphs are regular graphs based on Cayley graphs defined on the Abelian group \(\mathbb{Z}_{n}\) . They are popular network topologies that arise in distributed computing. Using number theoretical tools, we first prove two main results for random directed k-regular circulant graphs with n vertices, when n is sufficiently large and k is fixed. First, for any fixed ε>0, n=p prime and L≥p ^1/k (logp)^1+1/k+ε , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm that for almost all undirected 2r-regular circulant graphs finds a vertex bisector and an edge bisector, both of size less than n ^1?1/r+o(1). We then prove that the latter result also holds for all (rather than for almost all) 2r-regular circulant graphs with n=p, prime, vertices, while, in general, it does not hold for composite n. Using the bisection results, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. We introduce generic distributed algorithms to solve the gossip problem in any circulant graphs. We illustrate the efficiency of these algorithms by giving nearly matching upper bounds of the number of rounds required by these algorithms in the vertex-disjoint and the edge-disjoint paths communication models in particular circulant graphs.     

Computing the Scattering Number of Graphs

The scattering number of a noncomplete connected graph G is defined by s ( G )= max{ y ( G m X ) m X X ² V ( G ), y ( G m X ) S 2}, where y ( G m X ) denotes the number of components of G m X . This parameter can be used to measure the vulnerability of networks. It shows not only the difficulty to break down the network but also the damage that has been caused. In this paper, we prove that the problem of computing the scattering number of a graph is NP-complete. At the same time, the scattering numbers of grids and those of Cartesian products of two complete graphs are determined.     

On the Crossing Number of Complete Graphs

Let (G) denote the rectilinear crossing number of a graph G. We determine (K₁₁)=102 and (K₁₂)=153. Despite the remarkable hunt for crossing numbers of the complete graph K_n – initiated by R. Guy in the 1960s – these quantities have been unknown forn>10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size 11. Based on these findings, we establish a new upper bound on (K_n) for general n. The bound stems from a novel construction of drawings of K_n with few crossings.     

On the Stab Number of Rectangle Intersection Graphs

Theory of Computing Systems - We introduce the notion of stab number and exact stab number of rectangle intersection graphs, otherwise known as graphs of boxicity at most 2. A graph G is said to be...     

Crossing Number and Weighted Crossing Number of Near-Planar Graphs

A nonplanar graph G is near-planar if it contains an edge e such that G−e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hliněny and Salazar (Graph Drawing GD’06). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs.     

四正则图的交叉数

利用计算机对图的交叉数进行研究,给出了利用分支界限法计算图的交叉数的算法CCN(calculatecrossing number),并利用该算法计算出n≤12的所有四正则图的交叉数以及n≤16的随机四正则图的交叉数.同时计算出n≤12的所有四正则图的平均交叉数Aac(n)和n≤16的随机四正则图的平均交叉数Aac(n),根据计算结果提出四正则图的平均交叉数为O(n相似文献   

Counting the Number of Perfect Matchings in K5-Free Graphs

Counting the number of perfect matchings in graphs is a computationally hard problem. However, in the case of planar graphs, and even for K_3,3-free graphs, the number of perfect matchings can be computed efficiently. The technique to achieve this is to compute a Pfaffian orientation of a graph. In the case of K₅-free graphs, this technique will not work because some K₅-free graphs do not have a Pfaffian orientation. We circumvent this problem and show that the number of perfect matchings in K₅-free graphs can be computed in polynomial time. We also parallelize the sequential algorithm and show that the problem is in TC². We remark that our results generalize to graphs without singly-crossing minor.     

Lower Bound on the Minimum Number of Edges in Subgraphs of Johnson Graphs

Problems of Information Transmission - We prove a new lower bound on the minimum number of edges in subgraphs of Johnson graphs in the general case.     

Minimal Expansions in Redundant Number Systems and Shortest Paths in Graphs

We consider digit expansions in redundant number systems to base q with and consider such an expansion as minimal, if is minimal. We describe an efficient algorithm for determining a minimal representation and give an explicit characterization of optimal representations for odd q. Received: July 20, 1999; revised August 23 1999     

A Linear-Time Algorithm for Star-Shaped Drawings of Planar Graphs with the Minimum Number of Concave Corners

A star-shaped drawing of a graph is a straight-line drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. In this paper, we consider the problem of finding a star-shaped drawing of a biconnected planar graph with the minimum number of concave corners. We first show new structural properties of planar graphs to derive a lower bound on the number of concave corners. Based on the lower bound, we prove that the problem can be solved in linear time by presenting a linear-time algorithm for finding a best plane embedding of a biconnected planar graph with the minimum number of concave corners. This is in spite of the fact that a biconnected planar graph may have an exponential number of different plane embeddings.     

利用图的边分割集个数比较网络的可靠性

图的边分割个数是网络可靠性研究的一个重要参考指标。对给定n点e条边的图G,本文给出了用代数组合方法计算其边分割集的一般求法,然后用所求得的边分割集个数比较两个网络的可靠性。     

Exploiting Random Walks for Learning

In this paper we consider an approach to passive learning. In contrast to the classical PAC model we do not assume that the examples are independently drawn according to an underlying distribution, but that they are generated by a time-driven process. We define deterministic and probabilistic learning models of this sort and investigate the relationships between them and with other models. The fact that successive examples are related can often be used to gain additional information similar to the information gained by membership queries. We show how this can be used to design on-line prediction algorithms. In particular, we present efficient algorithms for exactly identifying Boolean threshold functions and 2-term RSE, and for learning 2-term-DNF, when the examples are generated by a random walk on {0,1}ⁿ.     

Walks in phylogenetic treespace

We prove that the spaces of unrooted phylogenetic trees are Hamiltonian for two popular search metrics: Subtree Prune and Regraft (SPR) and Tree Bisection and Reconnection (TBR). Further, we make progress on two conjectures of Bryant on searching phylogenetic treespace: treespace under the Nearest Neighbor Interchange (NNI) metric has a 2-walk, and there exist SPR neighborhoods without complete NNI walks.     

Number Matters: The Multimodality of Internet Use as an Indicator of the Digital Inequalities

This study explores the multimodality of Internet use as a critical indicator of digital inequalities. Rather than relying on traditional measures of user/nonuser and information/entertainment uses, this study focuses on a broad scope of online activities and investigates them collectively. Results show that the more modes of Internet activities people are engaged in, the more advanced uses they will add to their online behaviors. Female, older, poorer, and less educated only use the Internet for very limited basic applications, which are associated with fewer political communication and participation. While previous research concludes that the type of Internet activities matters, this study suggests that it is the number of types that matters in examining potential inequalities and their social consequences.     

Inequalities for the trace of matrix product

To obtain estimates of solutions of Lyapunov and Riccati equations which frequently occur in the stability analysis and optimal control design in linear control theory, many researchers have attempted to determine upper and lower bounds for the product of two matrices in terms of the trace of one matrix and the eigenvalues of the other. Baksalary and Puntanen claimed (“An inequality for the trace of matrix product”, ibid., vol. 37, no. 2, p. 239-40, 1992) that they had obtained a better estimate for the trace of the product of two matrices. The purpose of this note is to point out that their main result is incorrect and a counterexample is presented     

Quantum Random Walks in One Dimension

This letter treats the quantum random walk on the line determined by a 2 × 2 unitary matrix U. A combinatorial expression for the mth moment of the quantum random walk is presented by using 4 matrices, P, Q, R and S given by U. The dependence of the mth moment on U and initial qubit state is clarified. A new type of limit theorems for the quantum walk is given. Furthermore necessary and sufficient conditions for symmetry of distribution for the quantum walk is presented. Our results show that the behavior of quantum random walk is striking different from that of the classical ramdom walk. PACS: 03.67.Lx; 05.40.Fb; 02.50.Cw     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.