The Experts below are selected from a list of 321 Experts worldwide ranked by ideXlab platform
Saket Saurabh - One of the best experts on this subject based on the ideXlab platform.
-
ICALP - Approximate Counting of k-Paths: Deterministic and in Polynomial Space
2019Co-Authors: Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, Meirav ZehaviAbstract:A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)km∊−2)-time exponential-Space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ∊. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-Space algorithm with running time (2e)k+O(log3 k)m log n whenever ∊−1 = kO(1). Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4km∊−2)-time exponential-Space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. We present a deterministic 4k+O(√k(log2 k+log2 ∊−1))m log n-time Polynomial-Space algorithm. This matches the running time of the best known deterministic Polynomial-Space algorithm for deciding whether a given graph G has a path on k vertices. Additionally, we present a randomized 4k+O(log k(log k+log ∊−1))m log n-time Polynomial-Space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. Thus, the algorithm by Brand et al. runs in time 4k+o(k)m whenever ∊−1 = 2o(k), while our deterministic and randomized algorithms run in time 4k+o(k)m log n whenever ∊−1 = 2o(k 4 ) and 1 ∊−1 = 2o(log k k ), respectively. Prior to our work, no 2O(k)nO(1)-time Polynomial-Space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.
-
parameterized single exponential time Polynomial Space algorithm for steiner tree
SIAM Journal on Discrete Mathematics, 2019Co-Authors: Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, Petteri Kaski, Fahad PanolanAbstract:In the Steiner Tree problem, we are given as input a connected $n$-vertex graph with edge weights in $\{1,2,\ldots,W\}$, and a set of $k$ terminal vertices. Our task is to compute a minimum-weight ...
-
parameterized single exponential time Polynomial Space algorithm for steiner tree
International Colloquium on Automata Languages and Programming, 2015Co-Authors: Fedor V Fomin, Daniel Lokshtanov, Petteri Kaski, Fahad Panolan, Saket SaurabhAbstract:In the Steiner tree problem, we are given as input a connected \(n\)-vertex graph with edge weights in \(\{1,2,\ldots ,W\}\), and a subset of \(k\) terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time \({\mathcal O}(7.97^k\cdot n^4\cdot \log {W})\) using \({\mathcal O}(n^3\cdot \log {nW} \cdot \log k)\) Space. This is the first single-exponential time, Polynomial-Space FPT algorithm for the weighted Steiner Tree problem.
-
ICALP (1) - Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
Automata Languages and Programming, 2015Co-Authors: Fedor V Fomin, Daniel Lokshtanov, Petteri Kaski, Fahad Panolan, Saket SaurabhAbstract:In the Steiner tree problem, we are given as input a connected \(n\)-vertex graph with edge weights in \(\{1,2,\ldots ,W\}\), and a subset of \(k\) terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time \({\mathcal O}(7.97^k\cdot n^4\cdot \log {W})\) using \({\mathcal O}(n^3\cdot \log {nW} \cdot \log k)\) Space. This is the first single-exponential time, Polynomial-Space FPT algorithm for the weighted Steiner Tree problem.
-
WG - Planar k-path in subexponential time and Polynomial Space
Graph-Theoretic Concepts in Computer Science, 2011Co-Authors: Daniel Lokshtanov, Matthias Mnich, Saket SaurabhAbstract:In the k-Path problem we are given an n-vertex graph G together with an integer k and asked whether G contains a path of length k as a subgraph. We give the first subexponential time, Polynomial Space parameterized algorithm for k-Path on planar graphs, and more generally, on H-minor-free graphs. The running time of our algorithm is $O(2^{O(\sqrt{k}\log^2 k)}n^{O(1)})$ .
R. Tempone - One of the best experts on this subject based on the ideXlab platform.
-
discrete least squares Polynomial approximation with random evaluations application to parametric and stochastic elliptic pdes
Mathematical Modelling and Numerical Analysis, 2015Co-Authors: Abdellah Chkifa, G. Migliorati, F. Nobile, Albert Cohen, R. TemponeAbstract:Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for Polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that in the univariate case, the least-squares method is quasi-optimal in expectation in [A. Cohen, M A. Davenport and D. Leviatan. Found. Comput. Math. 13 (2013) 819–834] and in probability in [G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Found. Comput. Math. 14 (2014) 419–456], under suitable conditions that relate the number of samples with respect to the dimension of the Polynomial Space. Here “quasi-optimal” means that the accuracy of the least-squares approximation is comparable with that of the best approximation in the given Polynomial Space. In this paper, we discuss the quasi-optimality of the Polynomial least-squares method in arbitrary dimension. Our analysis applies to any arbitrary multivariate Polynomial Space (including tensor product, total degree or hyperbolic crosses), under the minimal requirement that its associated index set is downward closed. The optimality criterion only involves the relation between the number of samples and the dimension of the Polynomial Space, independently of the anisotropic shape and of the number of variables. We extend our results to the approximation of Hilbert Space-valued functions in order to apply them to the approximation of parametric and stochastic elliptic PDEs. As a particular case, we discuss “inclusion type” elliptic PDE models, and derive an exponential convergence estimate for the least-squares method. Numerical results confirm our estimate, yet pointing out a gap between the condition necessary to achieve optimality in the theory, and the condition that in practice yields the optimal convergence rate.
-
Discrete least squares Polynomial approximation with random evaluations - Application to parametric and stochastic elliptic PDEs
ESAIM: Mathematical Modelling and Numerical Analysis, 2015Co-Authors: Moulay Abdellah Chkifa, G. Migliorati, F. Nobile, Albert Cohen, R. TemponeAbstract:Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for Polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that in the univariate case, the least-squares method is quasi-optimal in expectation in \cite{CDL} and in probability in \cite{MNST2011}, under suitable conditions that relate the number of samples with respect to the dimension of the Polynomial Space. Here ``quasi-optimal'' means that the accuracy of the least-squares approximation is comparable with that of the best approximation in the given Polynomial Space. In this paper, we discuss the quasi-optimality of the Polynomial least-squares method in arbitrary dimension. Our analysis applies to any arbitrary multivariate Polynomial Space (including tensor product, total degree or hyperbolic crosses), under the minimal requirement that its associated index set is downward closed. The optimality criterion only involves the relation between the number of samples and the dimension of the Polynomial Space, independently of the anisotropic shape and of the number of variables. We extend our results to the approximation of Hilbert Space-valued functions in order to apply them to the approximation of parametric and stochastic elliptic PDEs. As a particular case, we discuss ``inclusion type'' elliptic PDE models, and derive an exponential convergence estimate for the least-squares method. Numerical results confirm our estimate, yet pointing out a gap between the condition necessary to achieve optimality in the theory, and the condition that in practice yields the optimal convergence rate.
-
Analysis of Discrete $$L^2$$ L 2
Foundations of Computational Mathematics, 2014Co-Authors: G. Migliorati, F. Nobile, E. Schwerin, R. TemponeAbstract:We analyze the problem of approximating a multivariate function by discrete least-squares projection on a Polynomial Space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the Polynomial Space. Optimality is meant in the sense that the weighted $$L^2$$ L 2 norm of the error committed by the random discrete projection is bounded with high probability from above by the best $$L^\infty $$ L ∞ error achievable in the given Polynomial Space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the Polynomial degree, and on the smoothness of the target function.
-
Analysis of Discrete $$L^2$$L2 Projection on Polynomial Spaces with Random Evaluations
Foundations of Computational Mathematics, 2014Co-Authors: G. Migliorati, F. Nobile, Erik Von Schwerin, R. TemponeAbstract:We analyze the problem of approximating a multivariate function by discrete least-squares projection on a Polynomial Space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the Polynomial Space. Optimality is meant in the sense that the weighted $$L^2$$ L 2 norm of the error committed by the random discrete projection is bounded with high probability from above by the best $$L^\infty $$ L ? error achievable in the given Polynomial Space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the Polynomial degree, and on the smoothness of the target function.
Fedor V Fomin - One of the best experts on this subject based on the ideXlab platform.
-
parameterized single exponential time Polynomial Space algorithm for steiner tree
SIAM Journal on Discrete Mathematics, 2019Co-Authors: Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, Petteri Kaski, Fahad PanolanAbstract:In the Steiner Tree problem, we are given as input a connected $n$-vertex graph with edge weights in $\{1,2,\ldots,W\}$, and a set of $k$ terminal vertices. Our task is to compute a minimum-weight ...
-
parameterized single exponential time Polynomial Space algorithm for steiner tree
International Colloquium on Automata Languages and Programming, 2015Co-Authors: Fedor V Fomin, Daniel Lokshtanov, Petteri Kaski, Fahad Panolan, Saket SaurabhAbstract:In the Steiner tree problem, we are given as input a connected \(n\)-vertex graph with edge weights in \(\{1,2,\ldots ,W\}\), and a subset of \(k\) terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time \({\mathcal O}(7.97^k\cdot n^4\cdot \log {W})\) using \({\mathcal O}(n^3\cdot \log {nW} \cdot \log k)\) Space. This is the first single-exponential time, Polynomial-Space FPT algorithm for the weighted Steiner Tree problem.
-
ICALP (1) - Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
Automata Languages and Programming, 2015Co-Authors: Fedor V Fomin, Daniel Lokshtanov, Petteri Kaski, Fahad Panolan, Saket SaurabhAbstract:In the Steiner tree problem, we are given as input a connected \(n\)-vertex graph with edge weights in \(\{1,2,\ldots ,W\}\), and a subset of \(k\) terminal vertices. Our task is to compute a minimum-weight tree that contains all the terminals. We give an algorithm for this problem with running time \({\mathcal O}(7.97^k\cdot n^4\cdot \log {W})\) using \({\mathcal O}(n^3\cdot \log {nW} \cdot \log k)\) Space. This is the first single-exponential time, Polynomial-Space FPT algorithm for the weighted Steiner Tree problem.
-
On exact algorithms for treewidth
ACM Transactions on Algorithms, 2012Co-Authors: Hans L. Bodlaender, Fedor V Fomin, Dieter Kratsch, Aries Koster, Dimitrios M. ThilikosAbstract:We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential Space or using only Polynomial Space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O*(2n). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the Traveling Salesman problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing Treewidth under the restriction that the Space used is only Polynomial and give a simple O*(4n) algorithm that requires Polynomial Space. We also show that with a more complicated algorithm using balanced separators, Treewidth can be computed in O*(2.9512n) time and Polynomial Space.
-
faster steiner tree computation in Polynomial Space
European Symposium on Algorithms, 2008Co-Authors: Fedor V Fomin, Fabrizio Grandoni, Dieter KratschAbstract:Given an n-node graph and a subset of kterminal nodes, the NP-hard Steiner tree problem is to compute a minimum-size tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62n)-time enumeration are based on dynamic programming, and require exponential Space. Motivated by the fact that exponential-Space algorithms are typically impractical, in this paper we address the problem of designing faster Polynomial-Space algorithms. Our first contribution is a simple Polynomial-Space O(6knO(logk))-time algorithm, based on a variant of the classical tree-separator theorem. This improves on trivial O(nk+ O(1)) enumeration for, roughly, k≤ n/4. Combining the algorithm above (for small k), with an improved branching strategy (for large k), we obtain an O(1.60n)-time Polynomial-Space algorithm. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals must exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. As a byproduct of our work, we also improve the (exponential-Space) time complexity of the problem from O(1.42n) to O(1.36n).
Jesper Nederlof - One of the best experts on this subject based on the ideXlab platform.
-
hamiltonian cycle parameterized by treedepth in single exponential time and Polynomial Space
Workshop on Graph-Theoretic Concepts in Computer Science, 2020Co-Authors: Jesper Nederlof, Michal Pilipczuk, Celine M F Swennenhuis, Karol WegrzyckiAbstract:For many algorithmic problems on graphs of treewidth \(t\), a standard dynamic programming approach gives an algorithm with time and Space complexity \(2^{\mathcal {O}(t)}\cdot n^{\mathcal {O}(1)}\). It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the Space complexity to Polynomial, while retaining time complexity of the form \(2^{\mathcal {O}(d)}\cdot n^{\mathcal {O}(1)}\), where \(d\) is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and Space complexity \(2^{\mathcal {O}(t\log t)}\cdot n^{\mathcal {O}(1)}\) on graphs of treewidth \(t\), but it is not clear how to convert them into time-efficient Polynomial Space algorithms for graphs of low treedepth.
-
hamiltonian cycle parameterized by treedepth in single exponential time and Polynomial Space
arXiv: Data Structures and Algorithms, 2020Co-Authors: Jesper Nederlof, Michal Pilipczuk, Celine M F Swennenhuis, Karol WegrzyckiAbstract:For many algorithmic problems on graphs of treewidth $t$, a standard dynamic programming approach gives an algorithm with time and Space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the Space complexity to Polynomial, while retaining time complexity of the form $2^{\mathcal{O}(d)}\cdot n^{\mathcal{O}(1)}$, where $d$ is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and Space complexity $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$ on graphs of treewidth $t$, but it is not clear how to convert them into time-efficient Polynomial Space algorithms for graphs of low treedepth. Cygan et al. (FOCS'11) introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and Space complexity $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$. Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time $2^{\mathcal{O}(d)}\cdot n^{\mathcal{O}(1)}$ and Polynomial Space usage. However, a number of important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper we clarify the situation by showing that Hamiltonian Cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit $5^d\cdot n^{\mathcal{O}(1)}$-time and Polynomial Space algorithms on graphs of treedepth $d$. The algorithms are randomized Monte Carlo with only false negatives.
-
Fast Polynomial-Space Algorithms Using Inclusion-Exclusion
Algorithmica, 2012Co-Authors: Jesper NederlofAbstract:Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in \(\mathcal{O}^{\star}(2^{k}c)\) time and \(\mathcal{O}^{\star}(c)\) Space, where the \(\mathcal{O}^{\star}\) notation omits terms bounded by a Polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give \(\mathcal{O}^{\star}(2^{n})\)-time Polynomial Space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new Polynomial Space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.
-
fast Polynomial Space algorithms using mobius inversion improving on steiner tree and related problems
International Colloquium on Automata Languages and Programming, 2009Co-Authors: Jesper NederlofAbstract:Given a graph with n vertices, k terminals and bounded integer weights on the edges, we compute the minimum Steiner Tree in ${\mathcal{O}^*}(2^k)$ time and Polynomial Space, where the ${\mathcal{O}^*}$ notation omits poly (n ,k ) factors. Among our results are also Polynomial-Space $\mathcal{O}^*(2^n)$ algorithms for several ${\mathcal{NP}}$-complete spanning tree and partition problems. The previous fastest known algorithms for these problems use the technique of dynamic programming among subsets, and require exponential Space. We introduce the concept of branching walks and extend the Inclusion-Exclusion algorithm of Karp for counting Hamiltonian paths. Moreover, we show that our algorithms can also be obtained by applying Mobius inversion on the recurrences used for the dynamic programming algorithms.
-
ICALP (1) - Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
Automata Languages and Programming, 2009Co-Authors: Jesper NederlofAbstract:Given a graph with n vertices, k terminals and bounded integer weights on the edges, we compute the minimum Steiner Tree in ${\mathcal{O}^*}(2^k)$ time and Polynomial Space, where the ${\mathcal{O}^*}$ notation omits poly (n ,k ) factors. Among our results are also Polynomial-Space $\mathcal{O}^*(2^n)$ algorithms for several ${\mathcal{NP}}$-complete spanning tree and partition problems. The previous fastest known algorithms for these problems use the technique of dynamic programming among subsets, and require exponential Space. We introduce the concept of branching walks and extend the Inclusion-Exclusion algorithm of Karp for counting Hamiltonian paths. Moreover, we show that our algorithms can also be obtained by applying Mobius inversion on the recurrences used for the dynamic programming algorithms.
Takeaki Uno - One of the best experts on this subject based on the ideXlab platform.
-
A Polynomial-time-delay and Polynomial-Space algorithm for enumeration problems in multi-criteria optimization ☆
European Journal of Operational Research, 2011Co-Authors: Yoshio Okamoto, Takeaki UnoAbstract:Abstract We propose a Polynomial-time-delay Polynomial-Space algorithm to enumerate all efficient extreme solutions of a multi-criteria minimum-cost spanning tree problem, while only the bi-criteria case was studied in the literature. The algorithm is based on the reverse search framework due to Avis and Fukuda. We also show that the same technique can be applied to the multi-criteria version of the minimum-cost basis problem in a (possibly degenerated) submodular system. As an ultimate generalization, we propose an algorithm to enumerate all efficient extreme solutions of a multi-criteria linear program. When the given linear program has no degeneracy, the algorithm runs in Polynomial-time delay and Polynomial Space. To best of our knowledge, they are the first Polynomial-time delay and Polynomial-Space algorithms for the problems.
-
Polynomial delay and Polynomial Space algorithms for mining closed sequences graphs and pictures in accessible set systems
SIAM International Conference on Data Mining, 2009Co-Authors: Hiroki Arimura, Takeaki UnoAbstract:In this paper, we study efficient closed pattern mining in a general framework of set systems, which are fam- ilies of subsets ordered by set-inclusion with a certain structure, proposed by Boley, Horvath, Poigne, Wrobel (PKDD'07 and MLG'07). By modeling semi-structured data such as sequences, graphs, and pictures in a set sys- tem, we systematically study efficient mining of closed patterns. For a class of accessible set systems with a tree-like structure, we present an efficient depth-first search algorithm that finds all closed sets in accessi- ble set systems without duplicates in Polynomial-delay and Polynomial-Space w.r.t. the total input size using efficient oracles for the membership test and the clo- sure computation for the pattern class. From the above results, we show that the closed pattern mining prob- lems are efficiently solvable both in time and Space for the following classes: convex hulls, picture patterns in 2-D planes, maximal bi-cliques, closed relational graphs, closed patterns for rigid motifs with wildcards.
-
SDM - Polynomial-delay and Polynomial-Space algorithms for mining closed sequences, graphs, and pictures in accessible set systems
2009Co-Authors: Hiroki Arimura, Takeaki UnoAbstract:In this paper, we study efficient closed pattern mining in a general framework of set systems, which are fam- ilies of subsets ordered by set-inclusion with a certain structure, proposed by Boley, Horvath, Poigne, Wrobel (PKDD'07 and MLG'07). By modeling semi-structured data such as sequences, graphs, and pictures in a set sys- tem, we systematically study efficient mining of closed patterns. For a class of accessible set systems with a tree-like structure, we present an efficient depth-first search algorithm that finds all closed sets in accessi- ble set systems without duplicates in Polynomial-delay and Polynomial-Space w.r.t. the total input size using efficient oracles for the membership test and the clo- sure computation for the pattern class. From the above results, we show that the closed pattern mining prob- lems are efficiently solvable both in time and Space for the following classes: convex hulls, picture patterns in 2-D planes, maximal bi-cliques, closed relational graphs, closed patterns for rigid motifs with wildcards.
-
An efficient Polynomial Space and Polynomial delay algorithm for enumeration of maximal motifs in a sequence
Journal of Combinatorial Optimization, 2006Co-Authors: Hiroki Arimura, Takeaki UnoAbstract:In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al. (2001), Pisanti et al. (2003) and Pelfrene et al. (2003), its output-Polynomial time computability has been still open. The main result of this paper is a Polynomial Space Polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n3) time per motif with O(n) Space, in particular O(n3) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional computational cost compared to usual frequent motif mining algorithms.
-
a Polynomial Space and Polynomial delay algorithm for enumeration of maximal motifs in a sequence
International Symposium on Algorithms and Computation, 2005Co-Authors: Hiroki Arimura, Takeaki UnoAbstract:In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in (Parida et al., CPM'01), (Pisanti et al.,MFCS'03) and (Pelfrene et al., CPM'03), its output-Polynomial time computability is still open. The main result of this paper is a Polynomial Space Polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n with O(n3) time per motif with O(n2) Space and O(n3) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lowerbound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach.