1,721,078 research outputs found
Computing the Rooted Triplet Distance Between Phylogenetic Networks
No full text10.1007/978-3-030-25005-8_24IWOCA290-303Ital
Covering with clubs: Complexity and approximability
No full textFinding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being s-club, which is a subgraph where each vertex is at distance at most s to the others. Here we consider the problem of covering a given graph with the minimum number of s-clubs. We study the computational and approximation complexity of this problem, when s is equal to 2 or 3. First, we show that deciding if there exists a cover of a graph with three 2-clubs is NP-complete, and that deciding if there exists a cover of a graph with two 3-clubs is NP-complete. Then, we consider the approximation complexity of covering a graph with the minimum number of 2-clubs and 3-clubs. We show that, given a graph G = (V,E) to be covered, covering G with the minimum number of 2-clubs is not approximable within factor (Formula Presented), for any ε>0, and covering G with the minimum number of 3-clubs is not approximable within factor O(|V|1-ε, for any ε>0. On the positive side, we give an approximation algorithm of factor 2|V|1/2log3/2|V| for covering a graph with the minimum number of 2-clubs
Finding the cyclic covers of a string
No full textWe introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any nonempty string X of length n, a factor W of X is called a cyclic cover if every position of X belongs to an occurrence of a cyclic shift of W. Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic cover problem requires finding all distinct cyclic covers of X. We present an algorithm that solves the cyclic cover problem in time. This is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate W, computing the regions of X covered by cyclic shifts of W, extending those factors, and taking the union of the results
Integrative methods for discovering generic CIS-regulatory motifs
Full text linkPh.DDOCTOR OF PHILOSOPH
Complexity of the Maximum k-Path Vertex Cover Problem
Full text linkThis paper introduces the maximum version of the k-path vertex cover problem, called the Maximum k-Path Vertex Cover problem (MaxPkVC for short): A path consisting of k vertices, i.e., a path of length k−1 is called a k-path. If a k-path Pk includes a vertex v in a vertex set S, then we say that S or v covers Pk . Given a graph G=(V,E) and an integer s, the goal of MaxPkVC is to find a vertex subset S⊆V of at most s vertices such that the number of k-paths covered by S is maximized. MaxPkVC is generally NP-hard. In this paper we consider the tractability/intractability of MaxPkVC on subclasses of graphs: We prove that MaxP3VC and MaxP4VC remain NP-hard even for split graphs and for chordal graphs, respectively. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP3VC can be solved in polynomial time
- …
