Neighborhood hypergraphs of bipartite graphs

Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the literature showing that matrix symmetrization is in fact NP‐hard; furthermore, it is equivalent with the problem of recognizing whether a hypergraph can be realized as the neighborhood hypergraph of a graph. There are several variants of the latter problem corresponding to the concepts of open, closed, or mixed neighborhoods. While all these variants are NP‐hard in general, one of them restricted to the bipartite graphs is known to be equivalent with graph isomorphism. Extending this result, we consider several other variants of the bipartite neighborhood recognition problem and show that they all are either polynomial‐time solvable, or equivalent with graph isomorphism. Also, we study uniqueness of neighborhood realizations of hypergraphs and show that, in general, for all variants of the problem, a realization may be not unique. However, we prove uniqueness in two special cases: for the open and closed neighborhood hypergraphs of the bipartite graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 69–95, 2008     

无爪图泛圈性的邻域并条件

证明了,若G是一个p-阶3-连通无爪图,p≠10,11,15,并对G中任意两个不相邻的点u和v,满足|N(u)∪N(v)|≥(p-1)/2,则G是泛圈图.     

General properties of some families of graphs defined by systems of equations

In this paper we present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. We show that the graphs in all such families possess some general properties including regularity and biregularity, existence of special vertex colorings, and existence of covering maps—hence, embedded spectra—between every two members of the same family. Another general property, recently discovered, is that nearly every graph constructed in this manner edge‐decomposes either the complete, or complete bipartite, graph which it spans. In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems. A short survey of the related results is included. We also show that the edge‐decomposition property allows one to improve existing lower bounds for some multicolor Ramsey numbers. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 65–86, 2001     

Neighborhood-following algorithms for linear programming

In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(n~(1/2)L)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.     

大洪水算法在平面选址问题中的应用

大洪水算法是通过模拟洪水上涨过程来进行全局寻优的启发式算法.针对连续优化问题,基于三种不同的邻域搜索策略对其进行改进,并针对一类平面选址问题进行应用测试.仿真结果表明,大洪水算法是一类简单高效的算法,可用于连续优化问题的求解.     

地磁车辆检测器抗邻车位干扰的磁场角度关系分析应用

利用地磁车检器进行停车位检测时,车检器检测轴方向、停车位方向以及地磁场方向之间的角度关系,影响车检器不同轴向的峰值与灵敏度,随意设置会产生邻车位干扰或对磁场扰动的灵敏度低等问题。本研究基于双轴向地磁车检器,在不同停车位方向下,对车检器各个轴向进行测试,找出的最佳指向在保证正向轴高峰值高灵敏度的同时,使侧向轴低峰值低灵敏度,在提高检测精度的同时,减少邻车位干扰问题。研究给出了经验公式,在各地实践中,均得到了良好的效果。     

Embeddings of submanifolds and normal bundles

This paper studies the embeddings of a complex submanifold S inside a complex manifold M; in particular, we are interested in comparing the embedding of S in M with the embedding of S as the zero section in the total space of the normal bundle NS of S in M. We explicitly describe some cohomological classes allowing to measure the difference between the two embeddings, in the spirit of the work by Grauert, Griffiths, and Camacho, Movasati and Sad; we are also able to explain the geometrical meaning of the separate vanishing of these classes. Our results hold for any codimension, but even for curves in a surface we generalize previous results due to Laufert and Camacho, Movasati and Sad.     

辛轨形群胚的辛邻域定理

本文给出一种几何的子轨形群胚的定义,还给出了判定子轨形群胚的依据,并证明了紧子轨形群胚的轨形管状邻域、紧辛子轨形群胚的辛邻域和紧Lagrangian子轨形群胚的Lagrangian邻域的存在性.     

基于邻域特征匹配的通用噪声滤波器

图像去噪是遥感图像复原的重要步骤。在去除图像噪声的同时希望尽可能多地保留图像的纹理细节信息。受较差的成像环境和图像数据远距离传输的影响,遥感图像中一般都含有较强的高斯-脉冲混合噪声,而在现有的图像去噪算法中,能够同时去除图像中的高斯-脉冲混合噪声的通用噪声滤波器很少。以非局部平均方法的滤波思想为基础,通过引入邻域相似度评价的概念和脉冲噪声探测器,提出了基于邻域特征匹配的通用噪声滤波器。实验结果表明:基于邻域特征匹配的通用噪声滤波器具备有很好地去除图像高斯-脉冲混合噪声的能力,在去除高斯-脉冲混合噪声的同时能够很好地保持图像的复杂纹理和精细细节,并且便于向DSP/FPGA多处理器平台上移植。     

Local and variable neighborhood search for the <Emphasis Type="Italic">k</Emphasis>-cardinality subgraph problem

The minimum weighted k-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly k edges whose sum of weights is minimum. For this NP-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.