We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of...
详细信息
We give a subexponential fixed parameter algorithm for one-sided crossing minimization. It runs in time, where n is the number of vertices of the given graph and parameter k is the number of crossings. The exponent of in this bound is asymptotically optimal assuming the Exponential Time Hypothesis and the previously best known algorithm runs in time. We achieve this significant improvement by the use of a certain interval graph naturally associated with the problem instance and a simple dynamic program on this interval graph. The linear dependency on n is also achieved through the use of this interval graph.
We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n - k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, f...
详细信息
We discuss and compare four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with (n - k) vertices on the perimeter and k vertices in the interior (hole vertices), that is, for a total of n vertices. All four algorithms rely on the same abstract divide-and-conquer scheme, which is made efficient by a variant of dynamic programming. They are essentially based on two simple observations about triangulations, which give rise to triangle splits and paths splits. While each of the first two algorithms uses only one of these split types, the last two algorithms combine them in order to achieve certain improvements and thus to reduce the time complexity. By discussing this sequence of four algorithms we try to bring out the core ideas as clearly as possible and thus strive to achieve a deeper understanding as well as a simpler specification of these approaches. In addition, we implemented all four algorithms in Java and report results of experiments we carried out with this implementation.
We describe an algorithm for the dominating set problem with time complexity O((4g +40)(k)n(2)) for graphs of bounded genus g greater than or equal to 1, where k is the size of the set. It has previously been shown th...
详细信息
We describe an algorithm for the dominating set problem with time complexity O((4g +40)(k)n(2)) for graphs of bounded genus g greater than or equal to 1, where k is the size of the set. It has previously been shown that this problem is fixedparameter tractable for planar graphs. We give a simpler proof for the previous O(8(k)n(2)) result for planar graphs. Our method is a refinement of the earlier techniques. (C) 2004 Elsevier Inc. All rights reserved.
We describe an algorithm for the dominating set problem with time complexity O((24g(2) + 24g + 1)(k) n(2)) for graphs of bounded genus g, where k is the size of the set. It has previously been shown that this problem ...
详细信息
ISBN:
(纸本)3540438661
We describe an algorithm for the dominating set problem with time complexity O((24g(2) + 24g + 1)(k) n(2)) for graphs of bounded genus g, where k is the size of the set. It has previously been shown that this problem is fixedparameter tractable for planar graphs. Our method is a refinement of the earlier techniques.
The constraint bipatite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k(1), k(2), is there a vertex cover taking at most k(1) vertices from on...
详细信息
The constraint bipatite vertex cover problem (CBVC for short) is as follows: given a bipartite graph G with n vertices and two positive integers k(1), k(2), is there a vertex cover taking at most k(1) vertices from one and at most k(2) vertices from the other vertex set of G? CBVC is NP-complete. It formalizes the spare allocation problem for reconfigurable arrays, an important problem from VLSI manufacturing. We provide a nontrivial so-called fixed parameter algorithm for CBVC, running in O(1.3999(k1+k2) + (k(1) + k(2))n) time. Our algorithm is efficient and practical for small values of k(1) and k(2), as occurring in applications. The analysis of the search tree is based on a novel bonus point system: after the processing of the search tree (which takes time exponential in k), a polynomial-time final analysis follows. Parts of the computation that would be normally done within the search-tree phase can be postponed;nevertheless, knowledge about the size of those parts can be used to reduce the length of the search paths land hence the depth of the search tree as a whole) by a sort of bonus points. (C) 2001 academic Press.
In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i....
详细信息
In the Block Graph Deletion problem, we are given a graph G on n vertices and a positive integer k, and the objective is to check whether it is possible to delete at most k vertices from G to make it a block graph, i.e., a graph in which each block is a clique. In this paper, we obtain a kernel with vertices for the Block Graph Deletion problem. This is a first step to investigate polynomial kernels for deletion problems into non-trivial classes of graphs of bounded rank-width, but unbounded tree-width. Our result also implies that Chordal Vertex Deletion admits a polynomial-size kernel on diamond-free graphs. For the kernelization and its analysis, we introduce the notion of 'complete degree' of a vertex. We believe that the underlying idea can be potentially applied to other problems. We also prove that the Block Graph Deletion problem can be solved in time .
Background: Given n strings s(1), ... , s(n) each of length l and a nonnegative integer d, the CLOSEST STRING problem asks to find a center string s such that none of the input strings has Hamming distance greater tha...
详细信息
Background: Given n strings s(1), ... , s(n) each of length l and a nonnegative integer d, the CLOSEST STRING problem asks to find a center string s such that none of the input strings has Hamming distance greater than d from s. Finding a common pattern in many - but not necessarily all - input strings is an important task that plays a role in many applications in bioinformatics. Results: Although the closest string model is robust to the oversampling of strings in the input, it is severely affected by the existence of outliers. We propose a refined model, the CLOSEST STRING WITH OUTLIERS (CSWO) problem, to overcome this limitation. This new model asks for a center string s that is within Hamming distance d to at least n - k of the n input strings, where k is a parameter describing the maximum number of outliers. A CSWO solution not only provides the center string as a representative for the set of strings but also reveals the outliers of the set. We provide fixed parameter algorithms for CSWO when d and k are parameters, for both bounded and unbounded alphabets. We also show that when the alphabet is unbounded the problem is W[1]-hard with respect to n - k, l, and d. Conclusions: Our refined model abstractly models finding common patterns in several but not all input strings. We initialize the study of the computability of this model and show that it is sensitive to different parameterizations. Lastly, we conclude by suggesting several open problems which warrant further investigation.
Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph algorithms community about this theory is that it is main...
详细信息
ISBN:
(纸本)9780898715385
Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known algorithms on different domination problems.
暂无评论