{X,Y}-Cyclacene Graphs with Next Nearest Neighbor Interactions

Eigensolutions of {X( = C,B,N),Y( = C,B,N)}-cyclacene graphs with next nearest neighbor (nnn) interactions have been obtained in analytical forms by adapting n-fold rotational symmetry followed by two-fold rotational symmetry (or a plane of symmetry). Expressions of eigensolution indicate the subspectral relationship among such cyclacenes with an even number of hexagonal rings e.g., eigenvalues of {X,Y}-di-cyclacene are found in the eigenspectra of all such even cyclacenes. Total π-electron energies and highest occupied molecular orbital and lowest unoccupied molecular orbital (HOMO–LUMO) gaps are calculated using the analytical expressions obtained and are found to vary negligibly with the variation of nnn interactions in such cyclacenes. Total π-electron energy is found to increase due to increase in restriction intensity of nnn interactions, whereas the HOMO–LUMO gap of polyacenecs having the even number of hexagonal rings and with one electron at each site (atom) decreases with increase in the restriction intensity since such systems contain degenerate half-filled HOMO (bonding or nonbonding) that are much more vulnerable for perturbations imposed through nnn interactions.     

Nonuniform linear array DOA estimation using EM criterion

In this letter, we address the problem of Direction of Arrival (DOA) estimation with nonuniform linear array in the context of sparse Bayesian learning (SBL) framework. The nonuniform array output is deemed as an incomplete-data observation, and a hypothetical uniform linear array output is treated as an unavailable complete-data observation. Then the Expectation-Maximization (EM) criterion is directly utilized to iteratively maximize the expected value of the complete-data log likelihood under the posterior distribution of the latent variable. The novelties of the proposed method lie in its capability of interpolating the actual received data to a virtual uniform linear array, therefore extending the achievable array aperture. Simulation results manifests the superiority of the proposed method over off-the-shelf algorithms, specially on circumstances such as low SNR, insufficient snapshots, and spatially adjacent sources.     

Wavefront reduction using graphs,neural networks and genetic algorithm

This paper presents an algorithm for nodal numbering in order to obtain a small wavefront. Element clique graphs are employed as the mathematical models of finite element meshes. A priority function containing five vectors is used, which can be viewed as a generalization of Sloan's function. These vectors represent different connectivity properties of the graph models. Unlike Sloan's algorithm, which uses two fixed coefficients, here, five coefficients are employed, based on an evaluation by artificial neural networks. The networks weights are obtained using a simple genetic algorithm. Examples are included to illustrate the performance of the present hybrid method. Copyright © 2004 John Wiley & Sons, Ltd.     

Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.     

Maximum Cardinality Search for Computing Minimal Triangulations of Graphs

We present a new algorithm, called MCS-M, for computing minimal triangulations of graphs. Lex-BFS, a seminal algorithm for recognizing chordal graphs, was the genesis for two other classical algorithms: LEX M and MCS. LEX M extends the fundamental concept used in Lex-BFS, resulting in an algorithm that not only recognizes chordality, but also computes a minimal triangulation of an arbitrary graph. MCS simplifies the fundamental concept used in Lex-BFS, resulting in a simpler algorithm for recognizing chordal graphs. The new algorithm MCS-M combines the extension of LEX M with the simplification of MCS, achieving all the results of LEX M in the same time complexity.     

Pancyclicity of recursive circulant graphs

In this paper, we study the existence of cycles of all lengths in the recursive circulant graphs, and we show a necessary and sufficient condition for the graph being pancyclic and bipancyclic.     

Tight upper bound on the number of edges in a bipartite K3,3-free or K5-free graph with an application

We show that an n-vertex bipartite K_3,3-free graph with n?3 has at most 2n−4 edges and that an n-vertex bipartite K₅-free graph with n?5 has at most 3n−9 edges. These bounds are also tight. We then use the bound on the number of edges in a K_3,3-free graph to extend two known NC algorithms for planar graphs to K_3,3-free graphs.     

Reliability models for computer systems: An overview including dataflow graphs

The reliability of a system is the probability that the system will perform its intended mission under given conditions. This paper provides an overview of the approaches to reliability modelling and identifies their strengths and weaknesses. The models discussed include structure models, simple stochastic models and decomposable stochastic models. Ignoring time-dependence, structure models give reliability as a function of the topological structure of the system. Simple stochastic models make direct use of the properties of underlying stochastic processes, while decomposable models consider more complex systems and analyse them through subsystems. Petri nets and dataflow graphs facilitate the analysis of complex systems by providing a convenient framework for reliability analysis.     

Parallelization of WHILE loops on pipelined architectures

Modulo scheduling theory can be applied successfully to overlap Fortran DO loops on pipelined computers issuing multiple operations per cycle both with and without special loop architectural support. This paper shows that a broader class of loops—REPEAT-UNTIL, WHILE, and loops with more than one exit, in which the trip count is not known beforehand—can also be overlapped efficiently on multiple-issue pipelined machines. The approach is described with respect to a specific machine model, but it can be extended to other models. Special features in the architecture, as well as compiler representations for accelerating these loop constructs, are discussed. Performance results are presented for a few select examples.An earlier version of this paper was presented at Supercomputing '90.     

不含4圈的最大简单图边数的下界

证明了具有不小于6个顶点的不包含4圈的简单图的最大可能边数的下界是2n-5。