Page 1 Next

Displaying 1 – 20 of 57

Showing per page

A generalization of the graph Laplacian with application to a distributed consensus algorithm

Guisheng Zhai (2015)

International Journal of Applied Mathematics and Computer Science

In order to describe the interconnection among agents with multi-dimensional states, we generalize the notion of a graph Laplacian by extending the adjacency weights (or weighted interconnection coefficients) from scalars to matrices. More precisely, we use positive definite matrices to denote full multi-dimensional interconnections, while using nonnegative definite matrices to denote partial multi-dimensional interconnections. We prove that the generalized graph Laplacian inherits the spectral...

An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube

Jing Zhang, Li Xu, Shu-ming Zhou, Wei Wu, Xiucai Ye (2015)

International Journal of Applied Mathematics and Computer Science

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of...

Asymptotic spectral analysis of generalized Erdős-Rényi random graphs

Song Liang, Nobuaki Obata, Shuji Takahashi (2007)

Banach Center Publications

Motivated by the Watts-Strogatz model for a complex network, we introduce a generalization of the Erdős-Rényi random graph. We derive a combinatorial formula for the moment sequence of its spectral distribution in the sparse limit.

Bounded expansion in web graphs

Silvia Gago, Dirk Schlatter (2009)

Commentationes Mathematicae Universitatis Carolinae

In this paper we study various models for web graphs with respect to bounded expansion. All the deterministic models even have constant expansion, whereas the copying model has unbounded expansion. The most interesting case turns out to be the preferential attachment model --- which we conjecture to have unbounded expansion, too.

Characterization of generic properties of linear structured systems for efficient computations

Christian Commault, Jean-Michel Dion, Jacob W. van der Woude (2002)


In this paper we investigate some of the computational aspects of generic properties of linear structured systems. In such systems only the zero/nonzero pattern of the system matrices is assumed to be known. For structured systems a number of characterizations of so-called generic properties have been obtained in the literature. The characterizations often have been presented by means of the graph associated to a linear structured system and are then expressed in terms of the maximal or minimal...

Controllability of partial differential equations on graphs

Sergei Avdonin, Victor Mikhaylov (2008)

Applicationes Mathematicae

We study boundary control problems for the wave, heat, and Schrödinger equations on a finite graph. We suppose that the graph is a tree (i.e., it does not contain cycles), and on each edge an equation is defined. The control is acting through the Dirichlet condition applied to all or all but one boundary vertices. Exact controllability in L₂-classes of controls is proved and sharp estimates of the time of controllability are obtained for the wave equation. Null controllability for the heat equation...

Discrétisation de zeta-déterminants d’opérateurs de Schrödinger sur le tore

Laurent Chaumard (2006)

Bulletin de la Société Mathématique de France

Nous donnons ici deux résultats sur le déterminant ζ -régularisé det ζ A d’un opérateur de Schrödinger A = Δ g + V sur une variété compacte . Nous construisons, pour = S 1 × S 1 , une suite ( G n , ρ n , Δ n ) G n est un graphe fini qui se plonge dans via ρ n de telle manière que ρ n ( G n ) soit une triangulation de et où  Δ n est un laplacien discret sur G n tel que pour tout potentiel V sur , la suite de réels det ( Δ n + V ) converge après renormalisation vers det ζ ( Δ g + V ) . Enfin, nous donnons sur toute variété riemannienne compacte ( , g ) de dimension inférieure ou égale à 3 ...

Embeddings of hamiltonian paths in faulty k-ary 2-cubes

Shiying Wang, Shurong Zhang (2012)

Discussiones Mathematicae Graph Theory

It is well known that the k-ary n-cube has been one of the most efficient interconnection networks for distributed-memory parallel systems. A k-ary n-cube is bipartite if and only if k is even. Let (X,Y) be a bipartition of a k-ary 2-cube (even integer k ≥ 4). In this paper, we prove that for any two healthy vertices u ∈ X, v ∈ Y, there exists a hamiltonian path from u to v in the faulty k-ary 2-cube with one faulty vertex in each part.

Currently displaying 1 – 20 of 57

Page 1 Next