Fast Parallel Reordering and Isomorphism Testing of k -Trees

Abstract. In this paper two problems on the class of k -trees, a subclass of the class of chordal graphs, are considered: the fast reordering problem and the isomorphism problem. An O(log ² n) time parallel algorithm for the fast reordering problem is described that uses O(nk(n-k)/\kern -1ptlog n) processors on a CRCW PRAM proving membership in the class NC for fixed k . An O(nk(k+1)!) time sequential algorithm for the isomorphism problem is obtained representing an improvement over the O(n ² k(k+1)!) algorithm of Sekharan (the second author) [10]. A parallel version of this sequential algorithm is presented that runs in O(log ² n) time using O((nk((k+1)!+n-k))/log n) processors improving on a parallel algorithm of Sekharan for the isomorphism problem [10]. Both the sequential and parallel algorithms use a concept introduced in this paper called the kernel of a k -tree.     

无向图同构判定的并行算法

提出了一种判别无向图同构的方法，该方法根据无向图的邻接矩阵的特征值来判别出图的同构关系，而不需要其它附加信息。同时给出用Jacobi方法求出无向图的邻接矩阵的特征值的一种并行算法，它可以在分布式存储的多处理的多处理机上实现。实验结果表明，此方法是快速有效的，能在较短的运算时间内给出判断结果。     

Finding Edge-Disjoint Paths in Partial k -Trees

For a given graph G and p pairs (s _i ,t _i ) , , of vertices in G , the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P _i , , connecting s _i and t _i . Many combinatorial problems can be efficiently solved for partial k -trees (graphs of treewidth bounded by a fixed integer k ), but the edge-disjoint paths problem is NP-complete even for partial 3 -trees. This paper gives two algorithms for the edge-disjoint paths problem on partial k -trees. The first one solves the problem for any partial k -tree G and runs in polynomial time if p=O( log n) and in linear time if p=O(1) , where n is the number of vertices in G . The second one solves the problem under some restriction on the location of terminal pairs even if . Received January 21, 1977; revised September 19, 1997.     

An Efficient Parallel Strategy for ComputingK-Terminal Reliability and Finding Most Vital Edges in 2-Trees and Partial 2-Trees

In this paper, we first develop a parallel algorithm for computingK-terminal reliability, denoted byR(G_K), in 2-trees. Based on this result, we can also computeR(G_K) in partial 2-trees using a method that transforms, in parallel, a given partial 2-tree into a 2-tree. Finally, we solve the problem of finding most vital edges with respect toK-terminal reliability in partial 2-trees. Our algorithms takeO(log n) time withC(m, n) processors on a CRCW PRAM, whereC(m, n) is the number of processors required to find the connected components of a graph withmedges andnvertices in logarithmic time.     

有限语料汉蒙统计机器翻译调序方法研究

自统计机器翻译技术出现以来,调序一直是语序差异显著的语言对互译系统中的关键问题,基于大规模语料训练的调序方法得到了广泛研究。目前汉蒙双语语料资源十分有限,使得现有的依赖于大规模语料和语言学知识的调序方法难以取得良好效果。该文对已有的相关研究进行了分析,提出了在有限语料条件下的汉蒙统计机器翻译调序方法。该方法依据语言学知识获取对译文语序影响显著的短语类型,研究这些短语类型的调序方案,并融入已有的调序模型实现调序的优化。实验表明该方法在有限语料条件下的效果提升显著。     

Evaluating Reordering Strategies for Cluster Identification in Parallel Coordinates

The ability to perceive patterns in parallel coordinates plots (PCPs) is heavily influenced by the ordering of the dimensions. While the community has proposed over 30 automatic ordering strategies, we still lack empirical guidance for choosing an appropriate strategy for a given task. In this paper, we first propose a classification of tasks and patterns and analyze which PCP reordering strategies help in detecting them. Based on our classification, we then conduct an empirical user study with 31 participants to evaluate reordering strategies for cluster identification tasks. We particularly measure time, identification quality, and the users’ confidence for two different strategies using both synthetic and real-world datasets. Our results show that, somewhat unexpectedly, participants tend to focus on dissimilar rather than similar dimension pairs when detecting clusters, and are more confident in their answers. This is especially true when increasing the amount of clutter in the data. As a result of these findings, we propose a new reordering strategy based on the dissimilarity of neighboring dimension pairs.     

A SimpleO(log N) Time Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs

Maximal outerplanar graphs constitute an important class of graphs, often encountered in various applications, e.g., computational geometry, robotics, etc. In this paper, we propose a parallel algorithm for testing the isomorphism of maximal outerplanar graphs. Given the ordered adjacency lists of the two graphs, the proposed algorithm tests their isomorphism inO(log N) time usingNprocessors, for graphs withNnodes on an EREW shared memory model, as well as on a hypercube arhitecture. When the adjacency matrices of the graphs are given, this algorithm can be redesigned onN²processors to run inO(log N) time.     

Parallel Construction of (a, b)-Trees

We present an optimal parallel algorithm for the construction of (a, b)-trees-a generalization of 2-3 trees, 2-3-4 trees, and B-trees. We show the existence of a canonical form for (a, b)-trees, with a very regular structure, which allows us to obtain a scalable parallel algorithm for the construction of a minimum-height (a, b)-tree with N keys in O(N/p + log log N) time using p ≤ N/log log N processors on the EREW-PRAM model, and in O(N/p) time using p ≤ N processors on the CREW model. We show that the average memory utilization for the canonical form is at least 50% better than that for the worst-case and is also better than that for a random (a, b)-tree. A significant feature of the proposed parallel algorithm is that its time-complexity depends neither on a nor on b, and hence our general algorithm is superior to earlier algorithms for parallel construction of B-trees.     

任意图的同构判定算法:特征向量法

在构建有效描述任意图邻接矩阵的基础上,分别计算2个矩阵的特征值所对应的特征向量,并依据它们的极大无关组寻找可能的同构对应关系.通过逐一考查全体特征值,实现图同构的判定并确定同构图的顶点对应关系.随着判定规模增大及图对称性增强,与已有方法相比,文中方法具有更高的同构判定效率.实验结果表明,在多数情况下该方法是快捷有效的.     

On Isomorphism Testing of Groups with Normal Hall Subgroups

A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index.SchurZassenhaus theorem states that every normal Hall subgroup has a complement subgroup,that is a set of coset representatives H which also forms a subgroup of G.In this paper,we present a framework to test isomorphism of groups with at least one normal Hall subgroup,when groups are given as multiplication tables.To establish the framework,we first observe that a proof of Schur-Zassenhaus theorem is constructive,and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products,and isomorphisms of the normal parts and complement parts.We then focus on the case when the normal subgroup is abelian.Utilizing basic facts of representation theory of finite groups and a technique by Le Gall (STACS 2009),we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators.For the case when the complement subgroup is elementary abelian,which does not necessarily have bounded number of generators,we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem,which asks whether two linear subspaces are the same up to permutation of coordinates.A solution to the latter can be obtained by a mild extension of the singly exponential (in the number of coordinates) time algorithm for code isomorphism problem developed recently by Babai et al.(SODA 2011).Enroute to obtaining the above reduction,we study the following computational problem in representation theory of finite groups: given two representations ρ and τ of a group H over Zpd,p a prime,determine if there exists an automorphism φ : H → H ,such that the induced representation ρφ = ρφ and τ are equivalent,in time poly(|H |,pd).     

Parallel string matching with k mismatches

Two improved algorithms for string matching with k mismatches are presented. One algorithm is based on fast integer multiplication algorithms whereas the other follows more closely classic string-matching techniques.     

无向图的层次化谱分析同构判定算法

针对无向图同构的判定问题,一种层次化的基于谱分析的同构判定算法.比较两图的顶点数、边数以及度数序列对图进行预同构判定;然后对具有唯一Fiedler向量的图通过层次化的谱分析算法进行再次同构判定.与最具代表性的同构判定算法Nauty相比,随着判定图的规模增大,该算法对于规则网格图和固定度数图具有更高的同构判定效率.     

一种多到一子图同构检测方法

提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.     

Finding the k Shortest Paths in Parallel

A concurrent-read exclusive-write PRAM algorithm is developed to find the k shortest paths between pairs of vertices in an edge-weighted directed graph. Repetitions of vertices along the paths are allowed. The algorithm computes an implicit representation of the k shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m+nk log ² k) work and O( log^3k log ^*k+ log n( log log k+ log ^*n)) time, assuming that a shortest path tree rooted at the destination is pre-computed. The paths themselves can be extracted from the implicit representation in O( log k + log n) time, and O(n log n +L) work, where L is the total length of the output. Received July 2, 1997; revised June 18, 1998.     

Definability Equals Recognizability of Partial 3-Trees and \sl k -Connected Partial \sl k -Trees

We consider graph decision problems on partial 3-trees that can be solved by a finite-state, leaf-to-root tree automaton processing a width-3 tree decomposition of the given graph. The class of yes-instances of such a problem is said to be recognizable by the tree automaton. In this paper we show that any such class of recognizable partial 3-trees is definable by a sentence in CMS logic. Here, CMS logic is the extension of Monadic Second-order logic with predicates to count the cardinality of sets modulo fixed integers. We also generalize this result to show that recognizability (by a tree automaton that processes width-k tree decompositions) implies CMS-definability for k -connected partial k -trees. The converse--definability implies recognizability--is known to hold for any class of partial k -trees, and even for any graph class with an appropriate definition of recognizability. It has been conjectured that recognizability implies definability over partial k -trees; but a proof was previously known only for k h 2 . This paper proves the conjecture, and hence the equivalence of definability and recognizability, over partial 3-trees and k -connected partial k -trees. We use techniques that may lead to a proof of this equivalence over all partial k -trees.     

素性检测的并行计算

提出了一种基于Java的素性检测并行计算的结构和实现方法,就RMI系统、多线程同步、容错与负载均衡等关键技术进行了讨论,并给出了实验结果及分析。