Robot Map Verification of a Graph World

In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and its orientation in the map, is correct for the world G. We consider the world model of a graph G = (V _G, E _G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. (This also holds for the map M = (V _M, E _M.) The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices (and edges) from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down at an edge of the graph world G and pick up later as needed. The robot can recognize the edge marker when it encounters it in the world G. By reducing the verification problem to an exploration problem, verification can be completed in O(|V _G| × |E _G|) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world (G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, IEEE Trans. on Robotics and Automation, vol. 7, pp. 859–865, 1991; Robotics and Autonomous Systems, vol. 22(2), pp. 159–178, 1997). In this paper, we show a strategy that verifies a map in O(|V _M|) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be planar (e.g., G may contain overpasses, tunnels, etc.).     

关于R(m=C4,n)图的优美性

本文对R(m=C4,n)图的优美性进行证明,同时对R(m=C4,n)图的交错性进行证明.     

典型液压系统在功率键合图中的应用

在工程系统动态特性的理论研究中,常用的方法有传递函数法和状态方程法。但对液压系统来说,具有一定的局限性。而功率键合图,则可以直接从液压原理图有条不紊地画出来。本文给出了一典型液压系统的功率键合图,同时给出了影响系统动态特性的各个因素和系统的方程。     

正则图的剖分图的秩

讨论几类正则图的剖分图的邻接矩阵的秩。主要有:圈,路,完全图,完全二部图和多部图,度为3与4的循环图。     

基于图上随机游动的 Web 页面布局可用性评价

针对Web页面布局可用性设计中缺乏实用的定量评价模型和方法的问题,根据扫描路径理论,使用视线跟踪法将网络用户在 Web 页面上的浏览行为模型化为注视点在赋权有限图上的随机游动,据此提出新颖实用的基于图上随机游动模型的Web页面布局可用性评价方法 (WLUE-RWG) ,并以淘宝商城和阿里巴巴的商品展示页面为例对其使用过程与效果进行验证,说明模型的可行性与方法的有效性．     

高等学校排考染色-匹配算法

将安排考试课程与分配班级考场分别化为图的染色与最大匹配问题，进而将两种算法融合并改进，使之适合于实际应用．最后以染色一匹配算法解决上海理工大学本科教学排考冲突问题为例，实证了算法的有效性．     

两类图的W-宽直径

图的直径与宽直径是并行与分布式网络通信延迟的度量,据此研究了两类图的W-宽直径,在n点圈Cn中添加t条边得到图C(n,t),讨论了图C(n,t)的2-宽直径的最小值问题,并得到其上下界,进而提出了h(n,t)精确取值的猜想;在分析联图连通度的基础上,导出了联图的W-宽直径上界估计式。     

Some sufficient conditions for the type 1 optimality of block designs

In this paper, we investigate the problem of determining block designs which are optimal under type 1 optimality criteria within various classes of designs having υ treatments arranged in b blocks of size k. The solutions to two optimization problems are given which are related to a general result obtained by Cheng (1978) and which are useful in this investigation. As one application of the solutions obtained, the definition of a regular graph design given in Mitchell and John (1977) is extended to that of a semi-regular graph design and some sufficient conditions are derived for the existence of a semi-regular graph design which is optimal under a given type 1 criterion. A result is also given which shows how the sufficient conditions derived can be used to establish the optimality under a specific type 1 criterion of some particular types of semi- regular graph designs having both equal and unequal numbers of replicates. Finally,some sufficient conditions are obtained for the dual of an A- or D-optimal design to be A- or D-optimal within an appropriate class of dual designs.     

Suppressing marginal totals from a two-dimensional table to protect sensitive information

The technique of data suppression for protecting sensitive information in a two-dimensional table from exact disclosure raises the computational problems of testing a given table of censored data for security, and searching for a secure suppression pattern of minimum size for a given table. We provide a polynomial security test to solve the former problem, and prove that the latter problem is intractable in the general case, but can be solved in linear time in the special case in which only sensitive cells are to be protected.     

Label‐ and Level‐Invariant Graphical Log‐Linear Models

We introduce two types of graphical log‐linear models: label‐ and level‐invariant models for triangle‐free graphs. These models generalise symmetry concepts in graphical log‐linear models and provide a tool with which to model symmetry in the discrete case. A label‐invariant model is category‐invariant and is preserved after permuting some of the vertices according to transformations that maintain the graph, whereas a level‐invariant model equates expected frequencies according to a given set of permutations. These new models can both be seen as instances of a new type of graphical log‐linear model termed the restricted graphical log‐linear model, or RGLL, in which equality restrictions on subsets of main effects and first‐order interactions are imposed. Their likelihood equations and graphical representation can be obtained from those derived for the RGLL models.