The pancyclicity and the Hamiltonian-connectivity of the generalized base-b hypercube

The interconnection network considered in this paper is the generalized base-b hypercube that is an attractive variance of the well-known hypercube. The generalized base-b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity and fault diameter. In this paper, we study the Hamiltonian-connectivity and pancyclicity of the generalized base-b hypercube by the algorithmic approach. We show that a generalized base-b hypercube is Hamiltonian-connected for b ? 3. That is, there exists a Hamiltonian path joining each pair of vertices in a generalized base-b hypercube for b ? 3. We also show that a generalized base-b hypercube is pancyclic for b ? 3. That is, it embeds cycles of all lengths ranging from 3 to the order of the graph for b ? 3.     

The Grid-Pyramid: A Generalized Pyramid Network

The Pyramid network is a desirable network topology used as both software data-structure and hardware architecture. In this paper, we propose a general definition for a class of pyramid networks that are based on grid connections between the nodes in each level. Contrary to the conventional pyramid network in which the nodes in each level form a mesh, the connections between these nodes may also be according to other grid-based topologies such as the torus, hypermesh or WK-recursive. Such pyramid networks form a wide class of interconnection networks that possess rich topological properties. We study a number of important properties of these topologies for general-purpose parallel processing applications. In particular, we prove that such pyramids are Hamiltonian-connected, i.e. for any arbitrary pair of nodes in the network there exists at least one Hamiltonian path between the two given nodes, and pancyclic, i.e. any cycle of length 3, 4 … and N, can be embedded in a given N-node pyramid network. It is also proven that two link-disjoint Hamiltonian cycles exist in the torus-pyramid and hypermesh-pyramid networks.     

Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=²n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given.     

On path bipancyclicity of hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. Based on Lemma 5, the authors of [C.-H. Tsai, S.-Y. Jiang, Path bipancyclicity of hypercubes, Inform. Process. Lett. 101 (2007) 93-97] showed that the n-cube Qn with n?3 is (2n−4)-path bipancyclicity. In this paper, counterexamples to the lemma are given, therefore, their proof fails. And we show the following result: The n-cube Qn with n?3 is (2n−4)-path bipancyclicity but is not (2n−2)-path bipancyclicity, moreover, and a path P of length k with 2?k?2n−4 lies in a cycle of length 2k−2 if and only if P contains two edges of dimension i for some i, 1?i?n. We conjecture that if 2n−4 is replaced by 2n−3, then the above result also holds.     

Hamiltonian paths and cycles passing through a prescribed path in hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. In this paper, the following result is obtained: The n-dimensional hypercube Qn with n?3 is (2n−3)-path bipancyclic but is not (2n−2)-path bipancyclic, moreover, a path P of length k with 2?k?2n−3 lies in a cycle of length 2k−2 if and only if P contains two edges of the same dimension. In order to prove the above result we first show that any path of length at most 2n−1 is a subpath of a Hamiltonian path in Qn with n?2, moreover, the upper bound 2n−1 is sharp when n?4.     

A Probabilistic Neural Network for Attribute Selection in Stereovision Matching

The key step in stereovision is image matching. This is carried out on the basis of selecting features, edge points, edge segments, regions, corners, etc. Once the features have been selected, a set of attributes (properties) for matching is chosen. This is a key issue in stereovision matching. This paper presents an approach for attribute selection in stereovision matching tasks based on a Probabilistic Neural Network, which allows the computation of a mean vector and a covariance matrix from which the relative importance of attributes for matching and the attribute interdependence can be derived. This is possible because the matching problem focuses on a pattern classification problem. The performance of the method is verified with a set of stereovision images and the results contrasted with a classical attribute selection method and also with the relevance concept. ID="A1" Correspondence and offprint requests to: Facultad de CC. Físicas, Universidad Complutense, 28040 Madrid, Spain. Email: pajares@dacya.ucm.es     

The load balancing problem in OTIS-Hypercube interconnection networks

An interconnection network architecture that promises to be an interesting option for future-generation parallel processing systems is the OTIS (Optical Transpose Interconnection System) optoelectronic architecture. Therefore, all performance improvement aspects of such a promising architecture need to be investigated; one of which is load balancing technique. This paper focuses on devising an efficient algorithm for load balancing on the promising OTIS-Hypercube interconnection networks. The proposed algorithm is called Clusters Dimension Exchange Method (CDEM). The analytical model and the experimental evaluation proved the excellence of OTIS-Hypercube compared to Hypercube in terms of various parameters, including execution time, load balancing accuracy, number of communication steps, and speed.

The repeater tree construction problem

A tree-like substructure on a computer chip whose task is to carry a signal from a source circuit to possibly many sink circuits and which consists only of wires and so-called repeater circuits is called a repeater tree. We present a mathematical formulation of the optimization problems related to the construction of such repeater trees. Furthermore, we prove theoretical properties of a simple iterative procedure for these problems which was successfully applied in practice.     

The bipancycle-connectivity of the hypercube

Paths and cycles are popular interconnection networks due to their simplicity and low degrees, and therefore an efficient way of embedding them into an interconnection network is of particular importance. Many path-embedding aspects and cycle-embedding aspects, such as Hamiltonicity, Hamiltonian-connectivity, panconnectivity, bipanconnectivity, pancyclicity, vertex-pancyclicity and edge-pancyclicity, have been proposed and extensively studied. In fact, these discussions are meaningful for interconnection networks of resource-allocated systems or heterogeneous computing systems. In this paper, we propose a new cycle-embedding aspect called bipancycle-connectivity that combines the concepts of vertex-pancyclicity and bipanconnectivity. A bipartite graph is bipancycle-connected if an arbitrary pair of vertices x, y is contained by common cycles called bipanconnected cycles that include a cycle of every even length ranging from minc(x, y) to N; where minc(x, y) denotes the length of the minimum cycle that contains x and y, and N is the number of vertices. In this paper, we introduce a new graph called the cycle-of-ladders. We show that the hypercube is bipancycle-connected by presenting algorithms to embed the cycle-of-ladders into the hypercube.     

复杂网络的分层递阶算法研究

复杂网络的计算方法研究在复杂网络建模方向起着不可或缺的作用,事实上,网络科学的建模在复杂网络领域研究最早、成果最多的一个方向,同样也是学术界广泛关注的一个重要的研究课题。在分析传统的网络节点遍历算法的基础上对节点遍历进行改进,重点介绍了复杂网络分层递阶算法的具体实现。复杂网络系统数值计算量大而繁琐,改进后的节点遍历法可以大大减少其运算量。文中提出的分层递阶算法可以较好满足一定范围内复杂网络数值计算的需求。     

基于掩码匹配的校园网出口流量抽样测量研究

针对校园网出口流量抽样测量问题，给出了测量点的选择及测量环境的设计方案,实施了特定掩码与IP报文标识字段进行匹配的抽样测量。提出了从抽样后的报文中估计一定时间刻度原始流量的大小、估计原始报文长度与协议分布的方法。通过对防火墙流量信息的观测和对校园网流量信息的分析表明，抽样测量结果与实际情况相符。     

Component-based construction of bio-pathway models: The parameter estimation problem

Constructing and analyzing large biological pathway models is a significant challenge. We propose a general approach that exploits the structure of a pathway to identify pathway components, constructs the component models, and finally assembles the component models into a global pathway model. Specifically, we apply this approach to pathway parameter estimation, a main step in pathway model construction. A large biological pathway often involves many unknown parameters and the resulting high-dimensional search space poses a major computational difficulty. By exploiting the structure of a pathway and the distribution of available experimental data over the pathway, we decompose a pathway into components and perform parameter estimation for each component. However, some parameters may belong to multiple components. Independent parameter estimates from different components may be in conflict for such parameters. To reconcile these conflicts, we represent each component as a factor graph, a standard probabilistic graphical model. We then combine the resulting factor graphs and use a probabilistic inference technique called belief propagation to obtain the maximally likely parameter values that are globally consistent. We validate our approach on a synthetic pathway model based on the Akt-MAPK signaling pathways. The results indicate that the approach can potentially scale up to large pathway models.     

Mean analysis of an online algorithm for the vertex cover problem

In 2005, Demange and Paschos proposed in [M. Demange, V.Th. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that, for any graph of maximum degree Δ, LR constructs a vertex cover whose size is at most Δ times the optimal one (this bound is tight in the worst case).Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125-127] that LR has interesting properties (it is a good “list algorithm” and it can easily be distributed). In addition, LR has good experimental behavior in spite of its Δ approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning.In this paper we analyze it deeper and we show that LR has good “average” performances: we prove that its mean approximation ratio is strictly less than 2 for any graph and is equal to 1+e−2≈1.13 in paths. LR is then a very interesting algorithm for constructing small vertex covers, despite its bad worst case behavior.     

Fractional snow cover mapping through artificial neural network analysis of MODIS surface reflectance

Accurate areal measurements of snow cover extent are important for hydrological and climate modeling. The traditional method of mapping snow cover is binary where a pixel is considered either snow-covered or snow-free. Fractional snow cover (FSC) mapping can achieve a more precise estimate of areal snow cover extent by estimating the fraction of a pixel that is snow-covered. The most common snow fraction methods applied to Moderate Resolution Imaging Spectroradiometer (MODIS) images have been spectral unmixing and an empirical Normalized Difference Snow Index (NDSI). Machine learning is an alternative for estimating FSC as artificial neural networks (ANNs) have been successfully used for estimating the subpixel abundances of other surfaces. The advantages of ANNs are that they can easily incorporate auxiliary information such as land cover type and are capable of learning nonlinear relationships between surface reflectance and snow fraction. ANNs are especially applicable to mapping snow cover extent in forested areas where spatial mixing of surface components is nonlinear. This study developed a multilayer feed-forward ANN trained through backpropagation to estimate FSC using MODIS surface reflectance, NDSI, Normalized Difference Vegetation Index (NDVI) and land cover as inputs. The ANN was trained and validated with higher spatial-resolution FSC maps derived from Landsat Enhanced Thematic Mapper Plus (ETM+) binary snow cover maps. Testing of the network was accomplished over training and independent test areas. The developed network performed adequately with RMSE of 12% over training areas and slightly less accurately over the independent test scenes with RMSE of 14%. The developed ANN also compared favorably to the standard MODIS FSC product. The study also presents a comprehensive validation of the standard MODIS snow fraction product whose performance was found to be similar to that of the ANN.     

表格在Word排版中的妙用

表格是用于排版的重要工具,可用来控制图像和文字的位置及大小,设计版面布局,本文结合具体应用实例,分析了表格在排版中的几个重要应用。     

The connectivity of exchanged crossed cube

The exchanged crossed cube, proposed by Li et al., is a new interconnection network having better properties than other variations of hypercube in the area of the fewer diameter, smaller links and lower cost factor. In this work we will show that the connectivity of exchanged crossed cube is equal to its minimum degree. Moreover each smallest cut in exchanged crossed cube is a neighborhood of some vertex.     

移动Ad hoc网络路由协议的研究--一种基于AODV路由协议的改进算法

Ad hoc网络是一种由移动节点组成、拓扑结构动态变化的自组织网络,网络不依赖于建设好的基础组织.在Ad hoc网络的研究中,一个非常重要的领域是路由问题,因为每个节点兼具主机和路由器的功能,这样就需要适合Ad hoc这种特殊环境的路由协议和路由算法.本文探讨了一种基于AODV路由协议(Ad hoc On-demand Distant Vector,按需距离矢量路由算法)的改进算法--按需距离矢量多径路由算法(AODVM算法),并对其性能进行了简单仿真分析,对研究可靠多径路由有一定的指导意义.     

Single-source three-disjoint path covers in cubes of connected graphs

A k-disjoint path cover (k-DPC for short) of a graph is a set of k internally vertex-disjoint paths from given sources to sinks that collectively cover every vertex in the graph. In this paper, we establish a necessary and sufficient condition for the cube of a connected graph to have a 3-DPC joining a single source to three sinks. We also show that the cube of a connected graph always has a 3-DPC joining arbitrary two vertices.     

基于聚类的BP网络在织物染色配色中的应用

针对织物染色配色过程中的复杂性和非线性问题,提出一种基于聚类的BP神经网络织物染色配色方法.通过模糊C均值聚类方法对初始样本集进行预处理,然后构建结构合理的BP神经网络对处理后的样本集进行训练和仿真.实验结果验证该方法与传统的BP神经网络相比能明显提高网络的收敛速度和泛化能力,能较准确地实现对织物染色配方的预测.