A Ford-Fulkerson type theorem concerning vector-valued flows in infinite networks
A generalization of the graph Laplacian with application to a distributed consensus algorithm
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...
A new formulation and solution of the sequencing problem: mathematical model
A New overlapping community detection algorithm based on similarity of neighbors in complex networks
Community detection algorithms help us improve the management of complex networks and provide a clean sight of them. We can encounter complex networks in various fields such as social media, bioinformatics, recommendation systems, and search engines. As the definition of the community changes based on the problem considered, there is no algorithm that works universally for all kinds of data and network structures. Communities can be disjointed such that each member is in at most one community or...
A stochastic complex network model society.
An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube
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...
Application de la théorie des graphes au choix des investissements à court terme dans un réseau électrique sujet à avaries
Asymptotic spectral analysis of generalized Erdős-Rényi random graphs
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.
Balancing cyclic -ary Gray codes.
Balancing cyclic -ary Gray codes. II.
Bounded expansion in web graphs
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.
Brève communication. Transformation du problème de partitionnement en un problème d'ensemble stable de poids maximal
Characterization of generic properties of linear structured systems for efficient computations
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
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...
De Bruijn cycles and their application for encoding of discrete positions
Diamètre de graphes et qualité de service d'un réseau de données
Discrétisation de zeta-déterminants d’opérateurs de Schrödinger sur le tore
Nous donnons ici deux résultats sur le déterminant -régularisé d’un opérateur de Schrödinger sur une variété compacte . Nous construisons, pour , une suite où est un graphe fini qui se plonge dans via de telle manière que soit une triangulation de et où est un laplacien discret sur tel que pour tout potentiel sur , la suite de réels converge après renormalisation vers . Enfin, nous donnons sur toute variété riemannienne compacte de dimension inférieure ou égale à ...
Embeddings of hamiltonian paths in faulty k-ary 2-cubes
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.
Exactly solvable and unsolvable shortest network problems in 3D-space.
Existence of feasible potentials on infinite networks.