无向图语言

无向图是图论中的基本概念,图半群是1991年提出的一个概念,形式语言与自动机理论是计算机科学与技术科学的重要基础理论。借助无向图和图半群,提出了无向图语言的概念,并研究了无向图语言的一个子类——平面图语言,给出了如下结论:一个无向图语言是平面图语言当且仅当它不包含K5语言或K3,3语言的剖分图语言。另外提出了几个开问题,其中之一是无向图语言与正则语言、上下文无关语言、上下文有关语言以及短语结构语言有何关系?     

基于无向图的选票版面结构理解算法

目前的选举系统或选票识别算法都简化了选票的版面理解,无法适应不同类型选票的准确定位、识别。该文在版面分割的基础上,提出一种基于无向图的选票版面结构描述方法,采用改进的深度优先遍历算法实现多种类型选票的准确定位和批量快速统计。实验证明,该方法具有选票设计灵活、精度高、通用性好、处理速度快等特点。     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

简单无向图的同构判定方法

给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 针对简单无向连通图的同构判定问题: 给出了基于距离矩阵特征多项式的同构判定条件; 进一步, 为避免计算误差对判定结果的影响, 给出了基于距离矩阵的秩与列和向量的同构判定条件. 上述两个判定条件均是充要条件且均具有多项式时间复杂度.     

简单无向图H性判定Determining the H Property of A Simple Undirected G

本文给出求解ＨＣ问题的一个多项式算法及其证明，实际运行也表明了算法的正确性。     

一种无向图的生成树算法

求无向图的生成树是在网络和回路分析中经常遇到的重要问题。文章描述采用计算树的方法求解无向图的生成树,这种方法是通过列举生成树之间的差别来实现的。     

混合图在无向图割集生成中的应用

为了进一步提高生成无向图割集的递归收缩算法的执行效率,将无向图转换为一类特殊的混合图,并将转换结果代替无向图输入递归收缩算法进行处理,修改了递归收缩算法中相应的算法步骤,使得改进算法可以更高效地生成无向图的割集.在理论上论证了改进算法的正确性,并通过理论分析和实验比较了改进算法和现有算法的时间复杂度和空间复杂度.理论分析结果和实验比较结果均表明改进算法明显比现有算法高效.     

一种特殊9阶无向图的探讨

采用例证法对9阶无向图中包含的5度顶点和6度顶点的每一种情况进行列举,并进行了深入探讨。     

基于无向图构建策略的主题句抽取

基于文档句构建无向图,将主题句的抽取问题转换为无向图中节点的权重计算问题。首先利用滑窗方法抽取主题词,构建空间向量并生成无向图,然后基于向量空间模型计算边权重,最后利用文档句相似度矩阵的权重模型对文档句权重进行建模与计算,依据压缩比得到文档的主题句。实验表明,该方法在不同的压缩比下生成的摘要质量高,主题句抽取结果接近于人工摘要,召回率和准确率综合指数较高。     

求无向图的所有Hamilton回路快速算法

引入单源单汇线性有向后k-部图,设计该结构上的删除算法、合并算法和输出算法.在此基础上给出判断无向图是否含有H回路的多项式算法和计算H回路数的多项式算法,最后给出求解无向图的所有H回路算法.该算法能比较有效地解决无向图中H回路的判定、计数和求解问题.     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

Log-space constructible universal traversal sequences for cycles of length O(n4.03)

The paper presents a simple construction of polynomial length universal traversal sequences for cycles. These universal traversal sequences are log-space (even NC¹) constructible and are of length O(n^4.03). Our result improves the previously known upper-bound O(n^4.76) for log-space constructible universal traversal sequences for cycles.     

基于静态分析的Android GUI遍历方法

针对传统软件安全测试方法（例如：符号执行、模糊测试、污点分析等）无法获得较高的Android程序图形用户界面（GUI）覆盖率的问题,提出动态和静态相结合的Android程序测试方法。该方法在静态分析Android应用程序数据流的基础之上,构建程序活动转换图和函数调用图,解析程序GUI元素,进而编写测试脚本动态遍历应用程序GUI元素。将该方法应用于订票日历、WiFi万能钥匙和360天气应用的实际测试,结果表明：Activity的平均覆盖率达到76%,明显高于人工测试的平均值30.08%和基于控件树遍历的42.05%~61.29%,该方法能够有效遍历Android应用程序GUI元素。     

IM-FTS:一种快速增量式频繁访问序列挖掘算法

由于Web数据增长迅速,先前的频繁序列随着序列库的更新而改变。若重新挖掘频繁序列会增加处理时间和数据存储量。提出一种改进的扩展格结构IE-LATTICE,存储先前的挖掘结果,并在其基础上提出一种基于双向约束的增量挖掘算法IM-FTS,在利用先前结果和约束策略前提下,算法仅从插入和删除序列中发现新的频繁序列。分析和实验表明算法能有效缩减数据处理时间和存储空间。     

A layout algorithm for undirected compound graphs

We present an algorithm for the layout of undirected compound graphs, relaxing restrictions of previously known algorithms in regards to topology and geometry. The algorithm is based on the traditional force-directed layout scheme with extensions to handle multi-level nesting, edges between nodes of arbitrary nesting levels, varying node sizes, and other possible application-specific constraints. Experimental results show that the execution time and quality of the produced drawings with respect to commonly accepted layout criteria are quite satisfactory. The algorithm has also been successfully implemented as part of a pathway integration and analysis toolkit named PATIKA, for drawing complicated biological pathways with compartmental constraints and arbitrary nesting relations to represent molecular complexes and various types of pathway abstractions.     

Optimal trade-off for Merkle tree traversal

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo [Fractal Merkle tree representation and traversal, in: RSA Cryptographers Track, RSA Security Conference, 2003] and M. Szydlo [Merkle tree traversal in log space and time, in: Proc. Eurocrypt, in: LNCS, vol. 3027, 2004, pp. 541–554; Merkle tree traversal in log space and time, Preprint version 2003, available at http://www.szydlo.com]. In particular, we show that our algorithm requires 2logn/log⁽³⁾n$2logn/{log}^{\left(3\right)}n$ hash function computations and storage for less than (logn/log⁽³⁾n+1)loglogn+2logn$(logn/{log}^{\left(3\right)}n+1)loglogn+2logn$ hash values, where n$n$ is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i.e. there is no algorithm that requires less than O(logn/logt)$O(logn/logt)$ time and less than O(tlogn/logt)$O(tlogn/logt)$ space for any choice of parameter t≥2$t\ge 2$.     

一种连通非加权图的快速聚类方法

图的聚类是数据聚类的一种很重要的变体,一方面通常可以用图来表示数据集中数据的相似度;另一方面对大型复杂网络的分析也引起人们越来越多地关注;而且对图进行聚类分析可以增强图的可视性,有助于可视化的分析、观测和导航。将最大最小方法的基本思想应用于非加权图的聚类,提出一种无向连通非加权图的快速聚类方法,该方法具有简单、聚类时间短、运行效率高、对于大型静态图的聚类具有良好的适应性等特点。     

Graph Traversal and Top-Down Evaluation of Logic Queries

In this paper,an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed.High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluation.In such a way,the subsumption checks and the identification of cyclic data can be done very efficiently.First,based on the subsumption checks,the search space can be reduced drastically by avoiding any redundant expansion operation.In fact,in the case of non-cyclic data,the proposed algorithm requires only linear time for evaluating a linear recursive query.On the other hand,in the case of cyclic data,by using the technique for isolaiting strongly connected components a lot of answers can be generatded directly in terms of the intermediate results and the relevant path information instead of evaluating them by performing algebraic operations.Since the cost of generating an answer in much less than that of evaluating an answer by algebraic operations,the bime consumption for cyclic data can be reduced by an order of magnitude or more.     

Gout-ITS系统的深度优先语义遍历算法

该文分析了痛风临床诊治智能教学系统（Intelligent Tutoring System for the Instruction of Gout Clinical Diagnosis and Treatment，以下简称Gout-ITS系统）自动生成病例所需的领域知识及其特点，提出了语义树知识表示法和深度优先语义遍历算法。该算法可以有效地生成既符合学生的学习难度要求、又符合病理逻辑的、多样化不重复的病例。最后，将该算法与人工智能中的深度优先搜索算法进行了比较，阐述了其中的不同之处。