Module Motif is a pattern matching problem that was introduced in the context of biological networks. Informally, given a multiset of colors P and a graph H whose nodes have sets of colors, it asks if P occurs in a mo...
详细信息
ISBN:
(纸本)9783642403132;9783642403125
Module Motif is a pattern matching problem that was introduced in the context of biological networks. Informally, given a multiset of colors P and a graph H whose nodes have sets of colors, it asks if P occurs in a module of H (i.e. in a set of nodes that have the same neighborhood outside the set). We present three parameterized algorithms for this problem that measure similarity between matched colors and handle deletions and insertions of colors to P. We observe that the running time of two of them might be essentially tight and prove that the problem is unlikely to admit a polynomial kernel.
We discuss approximability and inapproximability in FPT-time for a large class of subset problems where a feasible solution S is a subset of the input data. We introduce the notion of intersective approximability that...
详细信息
We discuss approximability and inapproximability in FPT-time for a large class of subset problems where a feasible solution S is a subset of the input data. We introduce the notion of intersective approximability that generalizes the one of safe approximability introduced in Guo et al. (2011) and show strong parameterized inapproximability results for many of the subset problems handled. (C) 2014 Elsevier B.V. All rights reserved.
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, whe...
详细信息
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2(O(log22 n)). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2(root log2 n) in expected polynomial time.
We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ) pr...
详细信息
We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ) problem. In both ANQ and TFNQ we have a pattern P and a graph H, and we seek a subgraph of H that resembles P. ANQ requires knowing the topology of P, while TFNQ ignores it. PINQ fits the scenario where partial information is available on the topology of P. Our main result is a parameterized algorithm that handles inputs for PINQ in which Pis a set of trees. This algorithm significantly improves the best known O* running time in solving TFNQ. We also improve the best known O* running times in solving two special cases of ANQ. (c) 2014 Elsevier B.V. All rights reserved.
The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a piecewise-linear ...
详细信息
The (parameterized) Minimum Link-Length Rectilinear Spanning Path problem in the d-dimensional Euclidean space R-d (d-RSP), for a given set S of n points in R-d and a positive integer k, is to find a piecewise-linear path P with at most k line-segments that covers (i.e., contains) all points in S, where all line-segments in P are axis-parallel. We first prove that the problem 2-RSP is NP-complete, improving the previously known result that the problem 10-RSP is NP-complete. We then consider a constrained d-RSP problem in which each line-segment s in the spanning path must cover all the points in the given set that share the same line with s. We present a new parameterized algorithm with running time O-center dot((2d)(k)) for the constrained d-RSP problem, which significantly improves the previous best result and is the first parameterized algorithm of running time O-center dot(k(O(k))) for the constrained d-RSP problem for a fixed d. We show that these results can be extended to the Minimum Link-Length Rectilinear Traveling Salesman problem.
parameterized algorithms and kernelization algorithms are presented for the weighted P-2-Packing problem, which is a generalization of the famous Graph Matching problem. The parameterized algorithms are based on the f...
详细信息
parameterized algorithms and kernelization algorithms are presented for the weighted P-2-Packing problem, which is a generalization of the famous Graph Matching problem. The parameterized algorithms are based on the following new techniques and observations: (1) new study on structure relationship between graph matchings in general graphs and P-2-packings in bipartite graphs;(2) an effective graph bi-partitioning algorithm;and (3) a polynomial-time algorithm for a constrained weighted P-2-Packing problem in bipartite graphs. The kernelization algorithms are based on the following new techniques: (1) the application of graph matching in kernelization;(2) a crown reduction structure for weighted problems. These techniques lead to randomized and deterministic parameterized algorithms that significantly improve the previous best upper bounds for the problem for both weighted and unweighted versions. For the kernelization algorithm, by using a weighted version of crown reduction, a kernel of size O(k(2)) is presented, where k is the given parameter of the problem. (C) 2013 Elsevier B.V. All rights reserved.
In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels L, a multiset P of labels f...
详细信息
In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels L, a multiset P of labels from L, a graph H = (V-H, E-H) and a function LabelH : V-H (->) 2(L), we need to find a subtree S of H which is an occurrence of P. We provide a parameterized algorithm with parameter k = vertical bar P vertical bar that runs in time O*(2(k)) and whose space complexity is polynomial. We also consider three variants of this problem. Then we address the alignment network query problem: Given two labeled graphs P and H, we need to find a subgraph S of H whose alignment with P is the best among all such subgraphs. We present two algorithms for cases in which P and H belong to certain families of DAGs. Their running times are polynomial and they are less restrictive than algorithms that are available today for alignment network queries. Topology-free and alignment network queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant. (C) 2014 Elsevier B.V. All rights reserved.
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) t...
详细信息
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) time algorithm for this problem, significantly improving the previous algorithm of time O(4k(3)n(5)) for the problem. Our result gives the first polynomial time algorithm for the MINIMUM NODE MULTIWAY CUT problem when the separator size is bounded by O(log n).
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) t...
详细信息
ISBN:
(纸本)3540739483
The parameterized NODE MULTIWAY CUT problem is for a given graph to find a separator of size bounded by k whose removal separates a collection of terminal sets in the graph. In this paper, we develop an O(k4(k)n(3)) time algorithm for this problem, significantly improving the previous algorithm of time O(4k(3)n(5)) for the problem. Our result gives the first polynomial time algorithm for the MINIMUM NODE MULTIWAY CUT problem when the separator size is bounded by O(log n).
In this paper, we present an O*(2.1479(k))-time algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most k or not, which is based on enumeration of vertex covers and improves ...
详细信息
In this paper, we present an O*(2.1479(k))-time algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most k or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most 2k and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as 'pseudo-cliques' and 'amortized transfer of cliques,' to analyze the running time bound. (C) 2012 Elsevier B.V. All rights reserved.
暂无评论