The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in outp...
详细信息
The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the general case. If, however, the transaction graphs are restricted to forests then the problem becomes tractable. In this paper we generalize the positive result on forests to graphs of bounded tree-width. In particular, we show that for this class of transaction graphs, frequent connected subgraphs can be listed in incremental polynomial time. Since subgraph isomorphism remains NP-complete for bounded tree-width graphs, the positive complexity result of this paper shows that efficient frequent pattern mining is possible even for computationally hard pattern matching operators. (C) 2010 Elsevier B.V. All rights reserved.
It is open whether the minimal hitting sets of a hypergraph can be listed in time polynomial in the input and output size. We show that a well-known sequential approach described by Berge and studied since the 1950s i...
详细信息
It is open whether the minimal hitting sets of a hypergraph can be listed in time polynomial in the input and output size. We show that a well-known sequential approach described by Berge and studied since the 1950s is not polynomial in the above sense, even if we allow an optimal ordering of the edges. This answers a question posed by H. Hirsh. The proof uses hypergraphs based on read-once formulas. We also offer a generalization of this sequential approach.
For a graph G in read-only memory on n vertices and m edges and a write-only output buffer, we give two algorithms using only O(n) rewritable space. The first algorithm lists all minimal a - b separators of G with a p...
详细信息
For a graph G in read-only memory on n vertices and m edges and a write-only output buffer, we give two algorithms using only O(n) rewritable space. The first algorithm lists all minimal a - b separators of G with a polynomial delay of O(nm). The second lists all minimal vertex separators of G with a cumulative polynomial delay of O(n(3)m). One consequence is that the algorithms can list the minimal a - b separators (and minimal vertex separators) spending O(nm) time (respectively, O(n(3)m) time) per object output. (C) 2010 Elsevier B.V. All rights reserved.
A multi-stack, O(n) space, constant amortized time algorithm is presented for listing all permutations of the integers 1,2,...,n that contain a subsequence of length k where all of the elements in the subsequence are ...
详细信息
A multi-stack, O(n) space, constant amortized time algorithm is presented for listing all permutations of the integers 1,2,...,n that contain a subsequence of length k where all of the elements in the subsequence are in increasing order. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
We consider families $\{ {\bf C}(n,k):O \leqq k \leqq n\} $ where each ${\bf C}(n,k)$ is a set of combinatorial objects, $C(n,k) = |{\bf C}(n,k)|$ satisfies a recursion $C(n,k)= a_{n,k}C(n - 1,k - 1) + b_{n,k} C(n - 1...
详细信息
We consider families $\{ {\bf C}(n,k):O \leqq k \leqq n\} $ where each ${\bf C}(n,k)$ is a set of combinatorial objects, $C(n,k) = |{\bf C}(n,k)|$ satisfies a recursion $C(n,k)= a_{n,k}C(n - 1,k - 1) + b_{n,k} C(n - 1,k)$, and each object in ${\bf C}(n,k)$ is represented by an n-vector. We study “loop-free” or “uniformly bounded transition” algorithms, i.e., algorithms which yield linear orders on the sets ${\bf C}(n,k)$ so that the vectors representing consecutive objects are “close to each other” (combinatorial Gray codes).Key words. listing algorithms, uniformly bounded operations, uniformly bounded transition algorithms, loop-free algorithms, binary reflected Gray codes, combinatorial Gray codes, binomial grids
We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159(n)). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a gr...
详细信息
We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159(n)). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159(n), thus improving on the trivial O(2(n)/root n) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exact algorithms. Based on this result, we derive an O(2.8718(n)) algorithm for the domatic number problem.
暂无评论