Computing the Treewidth and the Minimum Fill-In with the Modular Decomposition

Abstract. Using the notion of modular decomposition we extend the class of graphs on which both the treewidth and the minimum fill-in can be solved in polynomial time. We show that if C is a class of graphs that are modularly decomposable into graphs that have a polynomial number of minimal separators, or graphs formed by adding a matching between two cliques, then both the treewidth and the minimum fill-in on C can be solved in polynomial time. For the graphs that are modular decomposable into cycles we give algorithms that use respectively O(n) and O(n ³ ) time for treewidth and minimum fill-in.     

限制树宽的图的最小标记生成数算法

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。     

Computing Minimum Area Homologies

Calculating and categorizing the similarity of curves is a fundamental problem which has generated much recent interest. However, to date there are no implementations of these algorithms for curves on surfaces with provable guarantees on the quality of the measure. In this paper, we present a similarity measure for any two cycles that are homologous, where we calculate the minimum area of any homology (or connected bounding chain) between the two cycles. The minimum area homology exists for broader classes of cycles than previous measures which are based on homotopy. It is also much easier to compute than previously defined measures, yielding an efficient implementation that is based on linear algebra tools. We demonstrate our algorithm on a range of inputs, showing examples which highlight the feasibility of this similarity measure.     

Computing Modular Invariants of p-groups

Let V be a finite dimensional representation of a p -group, G, over a field,k , of characteristic p. We show that there exists a choice of basis and monomial order for which the ring of invariants, k [ V ]^G, has a finite SAGBI basis. We describe two algorithms for constructing a generating set for k [ V ] G. We use these methods to analyse k [2V₃ ]^U₃where U₃is the p -Sylow subgroup ofGL₃ (F_p) and 2 V₃is the sum of two copies of the canonical representation. We give a generating set for k [2 V₃]^U₃forp =  3 and prove that the invariants fail to be Cohen–Macaulay forp >  2. We also give a minimal generating set for k [mV₂ ]^Z / pwere V₂is the two-dimensional indecomposable representation of the cyclic group Z / p.     

计算两圆环面之间的最近距离

圆环面之间的距离计算是求解其碰撞检测和相交问题的基础.文中提出了一种判断两圆环之间包含、分离和相交3种位置关系,以及计算最近距离的方法.首先证明了空间两圆的Hausdorff距离可以通过计算共线法向点获得,并通过解一个一元八次方程求出三维空间中两圆的共线法向点;然后对共线法向点进行分类比较,得到两圆之间的最近距离和Hausdorff距离.证明了两圆环面间的位置关系不仅与其中心圆的最近距离相关,还与两中心圆的单向Hausdorff距离相关,进而解决了两圆环面之间的最近距离计算问题.最后通过实验说明了该方法的稳定性和高效性.     

Treewidth Lower Bounds with Brambles

In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower bounds, in particular when applied to (close to) planar graphs. This work was partially supported by the Netherlands Organisation for Scientific Research NWO (project Treewidth and Combinatorial Optimisation) and partially by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4).     

Computing H-Joins with Application to 2-Modular Decomposition

We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in |H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P ₄-join (aka N-join), P ₅-join (aka W-join), C ₆-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair {M ₁,M ₂} such that for every vertex x?(M ₁∪M ₂) and i∈{1,2}, x is either adjacent to all vertices in M _i or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127–139, 1987), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O(mn ²)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O(mn ³) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209–218, 1997), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex v∈G, G?v also has no module).     

Computing the Primary Decomposition of Zero-dimensional Ideals

Let K be an infinite perfect computable field and let I ⊆ K [ x ] be a zero-dimensional ideal represented by a Gröbner basis. We derive a new algorithm for computing the reduced primary decomposition of I using only standard linear algebra and univariate polynomial factorization techniques. In practice, the algorithm generally works in finite fields of large characteristic as well.     

一种求解最小诊断代价的小生境遗传算法

在诊断操作相关的情况下,求解最小代价的诊断操作序列的过程是一个NP完全问题．目前的算法在建模和求解方面都不：是十分理想．通过对诊断问题进行更精确的建模和分析,提出了求解最小诊断代价的小生境遗传算法NGAMECD（Niche Genetic Algorithm for Minimum ECD）．实验证明,算法NGAMECD具有良好的性质,它需要的空间可以预测,较普通的遗传算法具有更好的隐式并行性,执行过程中群体能够保持多样性,在有效避免早熟问题的同时算法的收敛速度较快．NGAMECD与P／C更新算法相比,诊断代价减少了20％～50％．     

Matrix-Based Genetic Algorithm for Computing the Minimum Volume Ellipsoid

The minimum volume ellipsoid (MVE) is a useful tool in multivariate statistics and data mining. It is used for computing robust multivariate outlier diagnostics and for calculating robust covariance matrix estimates. Various search algorithms for finding or approximating the MVE have been developed, but due to the combinatorial nature of the problem, exact computation of the MVE is impractical for all but the smallest datasets. Since large datasets are increasingly common, alternative algorithms are desired. Even among small datasets, performance of the existing algorithms varies considerably—no single algorithm dominates in performance. This paper presents a unique matrix-structured genetic algorithm (GA) that directly searches the ellipsoid space for the MVE. By directly searching the space of ellipsoids, the impact of the combinatorial nature of the problem is minimized. The matrix-structured GA is described in detail, and evidence is provided to illustrate the performance of the new algorithm in detecting multivariate outliers.      

平面代数曲线间最近距离的计算

通过几何观察,指出一条曲线上的最近点是另一条曲线的等距曲线与该曲线的切点这一事实,同时提出基于等距思想的方法来求解2条平面代数曲线间的最近距离．该方法几何意义明显,可同时用来计算代数曲线／参数曲线间的最近距离．对于平面二次曲线,采用文中方法得到的单变量多项式方程次数比已有类似方法中结果方程的次数更低,从而可以降低方程求解的计算复杂度或提高求解的稳定性．     

Computing Minimum Cuts by Randomized Search Heuristics

We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bi-criteria approach based on the famous maximum-flow minimum-cut theorem that enables evolutionary algorithms to find an optimal solution in expected polynomial time.     

Computing 3D Shape Guarding and Star Decomposition

This paper proposes an effective framework to compute the visibility guarding and star decomposition of 3D solid shapes. We propose a progressive integer linear programming algorithm to solve the guarding points that can visibility cover the entire shape; we also develop a constrained region growing scheme seeded on these guarding points to get the star decomposition. We demonstrate this guarding/decomposition framework can benefit graphics tasks such as shape interpolation and shape matching/retrieval.     

Applying Modular Decomposition to Parameterized Cluster Editing Problems

A graph G is said to be a bicluster graph if G is a disjoint union of bicliques (complete bipartite subgraphs), and a cluster graph if G is a disjoint union of cliques (complete subgraphs). In this work, we study the parameterized versions of the NP-hard Bicluster Graph Editing and Cluster Graph Editing problems. The former consists of obtaining a bicluster graph by making the minimum number of modifications in the edge set of an input bipartite graph. When at most k modifications are allowed (Bicluster(k) Graph Editing problem), this problem is FPT, and can be solved in O(4 ^k nm) time by a standard search tree algorithm. We develop an algorithm of time complexity O(4 ^k +n+m), which uses a strategy based on modular decomposition techniques; we slightly generalize the original problem as the input graph is not necessarily bipartite. The algorithm first builds a problem kernel with O(k ²) vertices in O(n+m) time, and then applies a bounded search tree. We also show how this strategy based on modular decomposition leads to a new way of obtaining a problem kernel with O(k ²) vertices for the Cluster(k) Graph Editing problem, in O(n+m) time. This problem consists of obtaining a cluster graph by modifying at most k edges in an input graph. A previous FPT algorithm of time O(1.92 ^k +n ³) for this problem was presented by Gramm et al. (Theory Comput. Syst. 38(4), 373–392, 2005, Algorithmica 39(4), 321–347, 2004). In their solution, a problem kernel with O(k ²) vertices is built in O(n ³) time.     

基于模块化分解的故障树分析方法

传统故障树分析算法存在诊断成本高和耗时长的问题,为此,在研究故障树结构中的特殊规律的基础上,采用深度优先最左遍历算法对故障树进行模块化分解,减小故障树分析的规模。结合if-then-else运算符,将最左底层模块子树转化为相应的二元决策图结构。运用深度优先最左遍历算法得到该二元决策图结构中的割集和最小割集,用相同故障概率的基本事件替代最左底层模块子树得到新故障树。采用自底向上、从左至右的递归综合分析思想,获得系统元件故障发生的概率,实现对故障树的分析。对故障实例的分析诊断结果表明,该方法可有效提高诊断速度,减少诊断成本。     

Compact Navigation and Distance Oracles for Graphs with Small Treewidth

Given an unlabeled, unweighted, and undirected graph with n vertices and small (but not necessarily constant) treewidth k, we consider the problem of preprocessing the graph to build space-efficient encodings (oracles) to perform various queries efficiently. We assume the word RAM model where the size of a word is Ω(logn) bits. The first oracle, we present, is the navigation oracle which facilitates primitive navigation operations of adjacency, neighborhood, and degree queries. By way of an enumeration argument, which is of interest in its own right, we show the space requirement of the oracle is optimal to within lower order terms for all graphs with n vertices and treewidth k. The oracle supports the mentioned queries all in constant worst-case time. The second oracle, we present, is an exact distance oracle which facilitates distance queries between any pair of vertices (i.e., an all-pairs shortest-path oracle). The space requirement of the oracle is also optimal to within lower order terms. Moreover, the distance queries perform in O(k ³log³ k) time. Particularly, for the class of graphs of popular interest, graphs of bounded treewidth (where k is constant), the distances are reported in constant worst-case time.