A time-space hierarchy between polynomial time and polynomial space

In this paper we define a natural time-space hierarchy $$P = F_0 \subseteq F_1 \subseteq F_2 \subseteq \cdot \cdot \cdot \subseteq PSPACE$$ between polynomial time and polynomial space and then study the relativizations of this hierarchy, obtaining a relative collapse and a relative proper hierarchy, at each possible level. Some partial results concerning relativized time-space tradeoff are given, together with some open questions.     

Extreme time-space tradeoffs for graphs with small space requirements

Two new isometric array languages, called Linear Array Languages (LAL) and Extended Regular Array Languages (ERAL), are introduced. A more abundant hierarchy for isometric languages is established. We show that some properties of two-dimensional array patterns do not coincide with their one-dimensional counterparts.     

时间-空间混和有限元

分析动力学与分析结构力学在数学理论上是一致的.振动与结构力学问题,其实只是一个符号之差.分析力学方法对两方面可通用.双曲型偏微分方程与椭圆型偏微分方程也是差一个符号.虽然性质不同,但分析上有共同之处.本文提出在有限元分析方面,不用对时间、空间分别离散而是组成混和的时空混和有限元网格.数值结果表明,时空混和有限元是有前途的.     

基于分层递阶商空间链的图连通性研究

图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次,通过构建图的分层递阶商空间链,分析不同层次商空间链中各节点分布情况,得出新的图连通性判定方法。与以往各判定方法相比,该方法具有易实现、效率高的优点,不仅能有效地判定图是否连通,还能确定图的连通分支数以及哪些节点位于同一连通分支中。     

贝叶斯网络概率推理中的空间优化方法

递归调节算法作为一种贝叶斯网络精确推理算法由于存储结果的个数是任意的,存储所占用的内存大小是可变的,所以该算法在空间上是自由的。然而当内存空间有限时,又希望节省计算时间,存储哪些计算结果就成了关键问题。针对此问题本文提出了应用深度优先分支定界法寻找存储占用空间的所有可能性,然后通过任意空间下推理时间的求解公式得到相应的推理时间,进而构造贝叶斯网络推理的时间—空间曲线,通过所构造的曲线找出最优离散存储策略,得到时间和空间之间的最佳的结合点,以最小时间代价换取了最大的存储空间。     

Component connectivity of generalized Petersen graphs

Let G be a simple non-complete graph of order n. The r-component edge connectivity of G denoted as λ_r (G) is the minimum number of edges that must be removed from G in order to obtain a graph with (at least) r connected components. The concept of r-component edge connectivity generalizes that of edge connectivity by taking into account the number of components of the resulting graph. In this paper we establish bounds of the r component edge connectivity of an important family of interconnection network models, the generalized Petersen graphs GP(n, k) in which n and k are relatively prime integers.     

增广泡型网络的边连通性和限制边连通性

针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端,采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法,证实了n维增广泡型网络中去除任意不多于n-1条边时,该增广泡型网络的任意两个节点之间依旧连通;通过构造最小限制边割的方法,证实了在不产生孤立节点的条件下,n维增广泡型网络中去除任意不多于2n-3条边时,该增广泡型网络的任意两个节点之间依旧连通。依据上述结果,通过实例证明增广泡型网络的容错能力优于泡型网络。     

Node connectivity and arc connectivity of a fuzzy graph

The fuzzy graph approach is more powerful in cluster analysis than the usual graph - theoretic approach due to its ability to handle the strengths of arcs effectively. The concept of node-strength sequence is introduced and is studied in a complete fuzzy graph. Two new connectivity parameters in fuzzy graphs namely, fuzzy node connectivity (κ) and fuzzy arc connectivity (κ^′) are introduced and obtained the fuzzy analogue of Whitney’s theorem. Fuzzy node cut, fuzzy arc cut and fuzzy bond are defined. Fuzzy bond is a special type of a fuzzy bridge. It is proved that at least one of the end nodes of a fuzzy bond is a fuzzy cutnode. It is shown that κ=κ^′ for a fuzzy tree and it is the minimum of the strengths of its strong arcs. The relationships of the new parameters with already existing vertex and edge connectivity parameters are studied and is shown that the value of all these parameters are equal in a compete fuzzy graph. Also a new clustering technique based on fuzzy arc connectivity is introduced.     

A polynomial time algorithm for an exact encoding of space containing

We address the problem of collision free navigation of a point robot among polygonal obstacles in a bounded known terrain in two dimensional space. The obstacles could be convex or concave polygons. We consider a combinatorial approach to the problem and focus on partitioning the terrain into distinct regions and encoding these regions. We then build a region-graph whose nodes represent the regions and every pair of neighbouring regions (nodes) are connected by an edge. We propose an o(n ₄) preprocessing algorithm to do this. This converts the problem of navigation from a source point to a destination point into a problem of finding a path in a planar graph from one of its nodes to another in O (n ₂ log n) time. The shortest path is derivable in 0(n ₄) time. The extension of the algorithm for three-dimensional space is also discussed.     

Component connectivity of the hypercubes

The r-component connectivity κ _r (G) of the non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, κ₂ is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q _n for r=2, 3, …, n+1, and we classify all the corresponding optimal solutions.     

On approximating metric 1-median in sublinear time

This paper focuses on approximating the metric 1-median problem with sublinear number of queries and time complexity. We first show a simper proof of the currently best 4-approximation algorithm, and then propose a recursive algorithm. For any integer h?2$h?2$, the algorithm finds a 2h  -approximation solution with O(n^1+1/h)$O(n^{1+1/h})$ queries and time complexity.     

超立方体网络的3路结构连通度及子结构连通度

针对以超立方体网络为蓝本的多处理机系统的可靠性和容错能力的精准度量问题，结合多处理机系统遭受计算机病毒攻击时常常发生结构性故障的特点，研究了n维超立方体网络的结构连通性和子结构连通性评价问题。首先，使用构造n维超立方体网络的3路结构割的方法得到其3路结构连通度的一个上界；然后，使用构造n维超立方体网络的3路子结构集的等价变换或约简变换的方法，得到其3路结构子连通度的一个下界；最后，利用任意网络的3路结构连通度不小于3路子结构连通度的性质，证实了超立方体网络的3路结构连通度和子结构连通度均为该超立方体网络维数的一半。这一结果表明，在3路结构故障模型下，破坏敌方以超立方体网络为底层拓扑的多处理系统至少需要攻击该系统中维数一半的3路结构或子结构。     

几何平均连接性指数:一种修正的分子连接性指数

本文试图改进Kier和Hall提出的分子连接性指数,提供一种更加完美的分子表征和分子设计技术。根据分子连接性指数定义,本文对其进行几何平均修正,使其更具解释性和丰富的含义,并命名为几何平均连接性指数(GMCI)。新的分子连接性指数用于一组含3-8个碳原子的烷烃7种性质的QSAR／QSPR研究,统计结果表明,由几何平均连接性指数所建模型普遍比传统的分子连接性指数所建模型要好。     

基于任务需求匹配的网络连通质量控制方法

现有多智能体系统网络研究方法缺乏对局部网络质量与区域性任务需求之间的匹配分析,这将影响任务的完成效率和质量,为此提出一种基于任务需求匹配的网络连通质量控制方法。首先,利用智能体移动状态分析系统网络的间歇连通性;然后,结合任务需求以及系统的间歇网络连通性构建基于主从模式的多智能体子网集合,进而从三个方面评估子网集合的连通质量;最后,提出基于网络连通质量控制的多智能体移动优化模型,用最大的子网集合连通质量表示多智能体网络连通质量,在智能体移动距离和网络连通质量的约束下求解任务完成率最大化的多智能体移动策略,通过该策略形成多智能体网络以执行任务。实验结果表明,该方法可以有效控制网络连通质量,维持任务完成率并提高智能体移动效用。     

Subdivision connectivity remeshing and its applications

This paper presents a subdivision connectivity remeshing approach for closed genus 0 meshes. It is based on spherical parameterization and umbrella‐operator smoothing. Our main contribution lies in adopting a low‐distortion spherical parameterization approach to generate high‐quality subdivision connectivity meshes. Besides, a simple and efficient point location method on the sphere based on the uniform partition of the rectangle is presented, which is used to find the containing triangle in the spherical mesh for each point on the sphere rapidly. Our method can generate high‐quality subdivision connectivity meshes fast, which can be applied to level of detail and progressive transmission. All the application examples demonstrate that our remeshing procedure is robust and efficient. Copyright © 2011 John Wiley & Sons, Ltd.