New spectral lower bounds on the bisection width of graphs

The communication overhead is a major bottleneck for the execution of a process graph on a parallel computer system. In the case of two processors, the minimization of the communication can be modeled using the graph bisection problem. The spectral lower bound of λ₂|V|/4 for the bisection width of a graph is widely known. The bisection width is equal to λ₂|V|/4 iff all vertices are incident to λ₂/2 cut edges in every optimal bisection.

We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion properties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on λ₂^β|V| with . We also present examples of graphs for which our new bounds are tight up to a constant factor. As a by-product, we derive new lower bounds for the bisection widths of 3- and 4-regular Ramanujan graphs.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

On handshakes in random graphs

In [Y. Métivier, N. Saheb, A. Zemmari, Analysis of a randomized rendezvous algorithm, Inform. and Comput. 184 (2003) 109-128], the authors introduce and analyze a randomized procedure to implement handshakes in graphs. In this paper, we investigate the same problem in random graphs. We prove results on the probability of success and we study the distribution of the random variable which counts the number of handshakes in the graph.     

Expander properties and the cover time of random intersection graphs

We investigate important combinatorial and algorithmic properties of _Gn,m,p$G_{n,m,p}$ random intersection graphs. In particular, we prove that with high probability (a) random intersection graphs are expanders, (b) random walks on such graphs are “rapidly mixing” (in particular they mix in logarithmic time) and (c) the cover time of random walks on such graphs is optimal (i.e. it is Θ(nlogn)$\Theta (nlogn)$). All results are proved for p$p$ very close to the connectivity threshold and for the interesting, non-trivial range where random intersection graphs differ from classical _Gn,p$G_{n,p}$ random graphs.     

On the independence number and Hamiltonicity of uniform random intersection graphs

In the uniform random intersection graphs model, denoted by G_n,m,λ, to each vertex v we assign exactly λ randomly chosen labels of some label set M of m labels and we connect every pair of vertices that has at least one label in common. In this model, we estimate the independence number α(G_n,m,λ), for the wide range m=⌊n^α⌋,α<1 and λ=O(m^1/4). We also prove the Hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief note concerning the independence number of G_n,m,p random intersection graphs, in which each vertex chooses labels with probability p.     

Statistical inference on attributed random graphs: Fusion of graph features and content

Many problems can be cast as statistical inference on an attributed random graph. Our motivation is change detection in communication graphs. We prove that tests based on a fusion of graph-derived and content-derived metadata can be more powerful than those based on graph or content features alone. For some basic attributed random graph models, we derive fusion tests from the likelihood ratio. We describe the regions in parameter space where the fusion improves power, using both numeric results from selected small examples and analytic results on asymptotically large graphs.     

Bounds on Mincut for Cayley Graphs over Abelian Groups

In this paper we find upper bounds for the mincut value of Cayley graphs over abelian groups. These results provide a significant improvement of those in Annextein and Baumslag (Math. Syst. Theory 26(3):271–291, [1993]). Partially supported by the Lynn and William Frankel Center for Computer Sciences.     

The distant-2 chromatic number of random proximity and random geometric graphs

We are interested in finding bounds for the distant-2 chromatic number of geometric graphs drawn from different models. We consider two undirected models of random graphs: random geometric graphs and random proximity graphs for which sharp connectivity thresholds have been shown. We are interested in a.a.s. connected graphs close just above the connectivity threshold. For such subfamilies of random graphs we show that the distant-2-chromatic number is Θ(logn) with high probability. The result on random geometric graphs is extended to the random sector graphs defined in [J. Díaz, J. Petit, M. Serna. A random graph model for optical networks of sensors, IEEE Transactions on Mobile Computing 2 (2003) 143-154].     

Lower bounds for sense of direction in regular graphs

A graph G with n vertices and maximum degree cannot be given weak sense of direction using less than colours. It is known that n colours are always sufficient, and it was conjectured that just are really needed, that is, one more colour is sufficient. Nonetheless, it has been shown [3] that for sufficiently large n there are graphs requiring more colours than . In this paper, using recent results in asymptotic graph enumeration, we show that (surprisingly) the same bound holds for regular graphs. We also show that colours are necessary, where d _G is the degree of G.Received: April 2002, Accepted: April 2003, Sebastiano Vigna: Partially supported by the Italian MURST (Finanziamento di iniziative di ricerca diffusa condotte da parte di giovani ricercatori).The results of this paper appeared in a preliminary form in Distributed Computing. 14th International Conference, DISC 2000, Springer-Verlag, 2000.     

A polynomial-time algorithm for computing K-terminal residual reliability of d-trapezoid graphs

Consider a probabilistic graph G   in which the edges of E(G)$E(G)$ are perfectly reliable, but the vertices of V(G)$V(G)$ may fail with some known probabilities. Given a subset K   of V(G)$V(G)$, the K-terminal residual reliability of G is the probability that all operational vertices in K are connected to each other. This problem can be considered to be a generalization of two well-known reliability problems – the K-terminal reliability problem and the residual connectedness reliability problem.     

Function-described graphs for modelling objects represented by sets of attributed graphs

We present in this article the model function-described graph (FDG), which is a type of compact representation of a set of attributed graphs (AGs) that borrow from random graphs the capability of probabilistic modelling of structural and attribute information. We define the FDGs, their features and two distance measures between AGs (unclassified patterns) and FDGs (models or classes) and we also explain an efficient matching algorithm. Two applications of FDGs are presented: in the former, FDGs are used for modelling and matching 3D-objects described by multiple views, whereas in the latter, they are used for representing and recognising human faces, described also by several views.     

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).     

Reconstruction of graphs based on random walks

The analysis of complex networks is of major interest in various fields of science. In many applications we face the challenge that the exact topology of a network is unknown but we are instead given information about distances within this network. The theoretical approaches to this problem have so far been focusing on the reconstruction of graphs from shortest path distance matrices. Often, however, movements in networks do not follow shortest paths but occur in a random fashion. In these cases an appropriate distance measure can be defined as the mean length of a random walk between two nodes — a quantity known as the mean first hitting time.In this contribution we investigate whether a graph can be reconstructed from its mean first hitting time matrix and put forward an algorithm for solving this problem. A heuristic method to reduce the computational effort is described and analyzed. In the case of trees we can even give an algorithm for reconstructing graphs from incomplete random walk distance matrices.     

Constructing vertex-disjoint paths in (n, k)-star graphs

This work describes a novel routing algorithm for constructing a container of width n − 1 between a pair of vertices in an (n, k)-star graph with connectivity n − 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004, pp. 160-165] already calculated the wide diameters in (n, n − 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 ? k ? n − 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 ? k ? ⌊n/2⌋ and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 ? k ? ⌊n/2⌋, or its diameter plus a value between 1 and 2 for ⌊n/2⌋ + 1 ? k ? n − 2.     

On generalization/specialization for conceptual graphs

Abstract

This paper centres on the generalization/specialization relation in the framework of conceptual graphs (this relation corresponds to logical subsumption when considering logical formulas associated with conceptual graphs). Results given here apply more generally to any model where knowledge is described by labelled graphs and reasoning is based on graph subsumption, as in semantic networks or in structural machine learning. The generalization/specialization relation, as defined by Sowa, is first precisely analysed, in particular its links with a graph morphism, called projection. Besides Sowa's specialization relation (which is a preorder), another one is actually used in some practical applications (which is an order). These are comparatively studied. The second topic of this paper is the design of efficient algorithms for computing these specialization relations. Since the associated problems are NP-hard, the form of the graphs is restricted in order to arrive at polynomial algorithms. In particular, polynomial algorithms are presented for computing a projection from a conceptual ‘tree’ to any conceptual graph, and for counting the number of such projections. The algorithms are also described in a generic way, replacing the projection by a parametrized graph morphism, and conceptual graphs by directed labelled graphs.     

Data reductions, fixed parameter tractability, and random weighted d-CNF satisfiability

Data reduction is a key technique in the study of fixed parameter algorithms. In the AI literature, pruning techniques based on simple and efficient-to-implement reduction rules also play a crucial role in the success of many industrial-strength solvers. Understanding the effectiveness and the applicability of data reduction as a technique for designing heuristics for intractable problems has been one of the main motivations in studying the phase transition of randomly-generated instances of NP-complete problems.In this paper, we take the initiative to study the power of data reductions in the context of random instances of a generic intractable parameterized problem, the weighted d-CNF satisfiability problem. We propose a non-trivial random model for the problem and study the probabilistic behavior of the random instances from the model. We design an algorithm based on data reduction and other algorithmic techniques and prove that the algorithm solves the random instances with high probability and in fixed-parameter polynomial time O(dknm) where n is the number of variables, m is the number of clauses, and k is the fixed parameter. We establish the exact threshold of the phase transition of the solution probability and show that in some region of the problem space, unsatisfiable random instances of the problem have parametric resolution proof of fixed-parameter polynomial size. Also discussed is a more general random model and the generalization of the results to the model.     

Exact prediction intervals for exponential lifetime based on random sample size

In this paper, we generalize the work by Lawless (1971) and Lingappaiah (1973) for predicting future order statistics from exponential lifetime when the sample size is a random variable. First, we derive the distributions of some pivotal quantities that can be used to predict future order statistics from exponential lifetime when the sample size is Poisson and binomial distributed. Next, we calculate the percentage points (factors) of the predictive distributions and use them to construct predictive confidence intervals for the future order statistics. To show the usefulness of our results, we present some simulation experiments. Finally, we apply our techniques to some real data sets in life testing.     

Detection of c, d, and e waves in the acceleration photoplethysmogram

Analyzing the acceleration photoplethysmogram (APG) is becoming increasingly important for diagnosis. However, processing an APG signal is challenging, especially if the goal is to detect its small components (c, d, and e waves). Accurate detection of c, d, and e waves is an important first step for any clinical analysis of APG signals. In this paper, a novel algorithm that can detect c, d, and e waves simultaneously in APG signals of healthy subjects that have low amplitude waves, contain fast rhythm heart beats, and suffer from non-stationary effects was developed. The performance of the proposed method was tested on 27 records collected during rest, resulting in 97.39% sensitivity and 99.82% positive predictivity.