The Cable-Trench Problem (CTP) is a common generalization of the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST): given an edge-weighted graph with a special root vertex and par...
详细信息
The Cable-Trench Problem (CTP) is a common generalization of the Single-Source Shortest Paths Problem (SSSP) and the Minimum Spanning Tree Problem (MST): given an edge-weighted graph with a special root vertex and parameters iota, gamma >= 0, the goal is to find a spanning tree that minimizes the total edge costs plus the total cost of the paths from each vertex to the root, scaled by iota and gamma, respectively. While it is well known that both SSSP and MST can be solved in polynomial time, CTP is NP-hard. We show that computing an approximate solution with factor less than 1.000475 is NP-hard, thus ruling out a polynomial-time approximation scheme, unless P = NP. We also consider the more general Steiner Cable-Trench Problem (SCTP), for which only a given subset of terminal vertices must be spanned by a solution. The tree might include non-terminal vertices, known as Steiner vertices, although only paths from terminals to the root are considered in the total cost. For this problem, we present a (2.88 +is an element of)-approximation based on a counting argument, for any is an element of > 0;also, we give a simple parameterized algorithm with the number of terminals as parameter. (c) 2023 Elsevier B.V. All rights reserved.
Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic al...
详细信息
Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kante[7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle. (c) 2009 Elsevier B.V. All rights reserved.
We present two parameterized algorithms for the closest string problem. The first runs in O(nL + nd . 17.97(d)) time for DNA strings and in O(nL + nd . 61.86(d)) time for protein strings, where n is the number of inpu...
详细信息
We present two parameterized algorithms for the closest string problem. The first runs in O(nL + nd . 17.97(d)) time for DNA strings and in O(nL + nd . 61.86(d)) time for protein strings, where n is the number of input strings, L is the length of each input string, and d is the given upper bound on the number of mismatches between the center string and each input string. The second runs in O(nL + nd . 13.92(d)) time for DNA strings and in O(nL + nd . 47.21(d)) time for protein strings. We then extend the first algorithm to a new parameterized algorithm for the closest substring problem that runs in O((n - 1)m(2) (L + d . 17.97(d) . m([log2 (d+1)]))) time for DNA strings and in O((n - 1)m(2) (L + d . 61.86(d) . m([log2 (d+1)]))) time for protein strings, where n is the number of input strings, L is the length of the center substring, L - 1 + m is the maximum length of a single input string, and d is the given upper bound on the number of mismatches between the center substring and at least one substring of each input string. All the algorithms significantly improve the previous bests. To verify experimentally the theoretical improvements in the time complexity, we implement our algorithm in C and apply the resulting program to the planted (L, d)-motif problem proposed by Pevzner and Sze in 2000. We compare our program with the previously best exact program for the problem, namely PMSPrune (designed by Davila et al. in 2007). Our experimental data show that our program runs faster for practical cases and also for several challenging cases. Our algorithm uses less memory too.
In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across...
详细信息
In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes, which lead to errors in decoding once a message is received. In particular, these sets correspond to variables that are not eventually corrected by the decoder, thus causing failures in decoding when using iterative algorithms. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. Furthermore, we prove that two of these trapping set problem variants are NP-hard for the first time. Additionally, we analyze these variants from the parameterized perspective. Finally, we model stopping set and trapping set problems as Integer Linear Programs (ILPs). The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896, 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP produces solutions efficiently and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.(1) (c) 2022 Elsevier B.V. All rights reserved.
Network planarization has been an important technique in numerous sensornet protocols-such as Greedy Perimeter Stateless Routing (GPSR), topology discovery, data-centric storage, etc.-however the planarization process...
详细信息
Network planarization has been an important technique in numerous sensornet protocols-such as Greedy Perimeter Stateless Routing (GPSR), topology discovery, data-centric storage, etc.-however the planarization process itself has been difficult. Known efficient planarization algorithms exist only for restrictive wireless network models: unit-disk graphs with accurately known location information. In this paper, we study efficient planarization of wireless sensor networks, and present a novel planarization method for a more general network model, where sensors can have non-uniform transmission ranges and no location information is needed. Our planarization algorithms also include a (2+epsilon)-approximation algorithm and an FPT algorithm for the bipartite planarization problem.
A sequence of exact algorithms to solve the VERTEX COVER and MAXIMUM INDEPENDENT SET problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size o...
详细信息
A sequence of exact algorithms to solve the VERTEX COVER and MAXIMUM INDEPENDENT SET problems have been proposed in the literature. All these algorithms appeal to a very conservative analysis that considers the size of the search tree, under a worst-case scenario, to derive an upper bound on the running time of the algorithm. In this paper we propose a different approach to analyze the size of the search tree. We use amortized analysis to show how simple algorithms, if analyzed properly, may perform much better than the upper bounds on their running time derived by considering only a worst-case scenario. This approach allows us to present a simple algorithm of running time O(1.194(k)k(2) + n) for the parameterized VERTEX COVER problem on degree-3 graphs, and a simple algorithm of running time O(1.1255 '') for the MAXIMUM INDEPENDENT SET problem on degree-3 graphs. Both algorithms improve the previous best algorithms for the problems.
We study techniques for solving the MAXIMUM SATISFIABILITY problem (MAxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization ...
详细信息
We study techniques for solving the MAXIMUM SATISFIABILITY problem (MAxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MAxSAT problem. As a result, we present an algorithm of time 0*(1.32481(k)) for the MAxSAT problem, improving the previous best upper bound 0*(1.358(k)) by Ivan Bliznets and Alexander Golovnev. (C) 2017 Elsevier B.V. All rights reserved.
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed pa...
详细信息
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper, we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop a randomized algorithm that, on given positive real numbers is an element of and delta, and a given set S of n triples and an integer k, produces a number h in time O(5.48(3k)n(2)ln(2/delta)/is an element of(2)) such that Prob[(1 - is an element of)h(0) <= h <= (1 + is an element of)h(0)] >= 1 - delta, where h(0) is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm developed by Karp, Luby and Madras.
We introduce a multivariate approach for solving weighted parameterized problems. By allowing flexible use of parameters, our approach defines a framework for applying the classic bounded search trees technique. In ou...
详细信息
We introduce a multivariate approach for solving weighted parameterized problems. By allowing flexible use of parameters, our approach defines a framework for applying the classic bounded search trees technique. In our model, given an instance of size n of a minimization/maximization problem, and a parameter W >= 1, we seek a solution of weight at most/at least W. We demonstrate the usefulness of our approach in solving VERTEX COVER, 3-HITTING SET, EDGE DOMINATING SET and MAX INTERNAL OUT-BRANCHING. While the best known algorithms for these problems admit running times of the form c(W)n(0(1)), for some c > 1, our framework yields running times of the form c(s)n(0(1)), where s <= W is the minimum size of a solution of weight at most/at least W. If no such solution exists, s = min{W, m}, where m is the maximum size of a solution. In addition, we analyze the parameter t <= s, the minimum size of a solution. (C) 2017 Elsevier Inc. All rights reserved.
Given a graph with labels defined on edges and a source-sink pair (s, t), the Label s-t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t. Similarly, ...
详细信息
Given a graph with labels defined on edges and a source-sink pair (s, t), the Label s-t Cut problem asks for a minimum number of labels such that the removal of edges with these labels disconnects s and t. Similarly, the Global Label Cut problem asks for a minimum number of labels to disconnect G itself. For these two problems, we identify two useful parameters, i.e., l(max), the maximum length of any s-t path (only applies to Label s-t Cut), and f(max), the maximum number of appearances of any label in the graph (applies to the two problems). We show that l(max) = 2 and f(max) = 2 are two complexity thresholds for Label s-t Cut Furthermore, we give (i) an O*(c(k)) time parameterized algorithm for Label s-t Cut With (l(max) bounded from above, where parameter k is the number of labels in a solution, and c is a constant with l(max) - 1 < c < l(max), (ii) a combinatorial l(max)-approximation algorithm for Label s-t Cut, and (iii) a polynomial time exact algorithm for Global Label Cut with f(max) bounded from above.. (C) 2016 Elsevier B.V. All rights reserved.
暂无评论