检索结果-内蒙古大学图书馆

On the complexity of the Cable-Trench Problem

DISCRETE APPLIED MATHEMATICS 2023年第1期340卷 272-285页

作者： Benedito, Marcelo P. L. Pedrosa, Lehilton L. C. Rosado, Hugo K. K. Univ Estadual Campinas Inst Comp Campinas Brazil

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.

关键词： Steiner tree Cable-trench Inapproximability Approximation Hardness parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

引用

DISCRETE APPLIED MATHEMATICS 2010年第7期158卷 851-867页

作者： Ganian, Robert Hlineny, Petr Masaryk Univ Fac Informat Brno 60200 Czech Republic

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.

关键词： Rank-width parameterized algorithm Myhill-Nerode theorem Graph colouring

来源：评论

学校读者我要写书评

暂无评论

Fast Exact algorithms for the Closest String and Substring Problems with Application to the Planted (L, d)-Motif Model

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第5期8卷 1400-1410页

作者： Chen, Zhi-Zhong Wang, Lusheng Tokyo Denki Univ Dept Math Sci Hatomaya Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

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.

关键词： parameterized algorithm closest string closest substring DNA motif discovery

来源：评论

学校读者我要写书评

暂无评论

On the complexity of and solutions to the minimum stopping and trapping set problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 915卷 26-44页

作者： Velasquez, Alvaro Subramani, K. Wojciechowski, Piotr AF Res Lab Informat Directorate Rome NY 13441 USA West Virginia Univ LCSEE Morgantown WV 26506 USA

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.

关键词： Stopping set Trapping set NP-complete parameterized algorithm Exact exponential algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Planarization of Wireless Sensor Networks

引用

algorithmICA 2011年第3期60卷 593-608页

作者： Zhang, Fenghui Jiang, Anxiao (Andrew) Chen, Jianer Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

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.

关键词： Sensor network Network planarization Graph drawing Bipartite planarization Approximation algorithm parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems

引用

algorithmICA 2005年第4期43卷 245-273页

作者： Chen, JN Kanj, IA Xia, G Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA DePaul Univ Sch CTI Chicago IL 60604 USA

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.

关键词： vertex cover independent set exact algorithm parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Dealing with 4-variables by resolution: An improved MaxSAT algorithm

引用

THEORETICAL COMPUTER SCIENCE 2017年 670卷 33-44页

作者： Chen, Jianer Xu, Chao Wang, Jianxin Cent South Univ Sch Informat Sci & Engn Changsha 410083 Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

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.

关键词： Maximum satisfiability parameterized algorithm Branch and bound The resolution principle

来源：评论

学校读者我要写书评

暂无评论

On Counting 3-D Matchings of Size k

引用

algorithmICA 2009年第4期54卷 530-543页

作者： Liu, Yunlong Chen, Jianer Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha 410083 Peoples R China Hunan Normal Univ Sch Further Educ Changsha 410012 Peoples R China Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

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.

关键词： 3-D matching parameterized algorithm Approximation algorithm Randomized algorithm Counting complexity

来源：评论

学校读者我要写书评

暂无评论

A multivariate framework for weighted FPT algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 89卷 157-189页

作者： Shachnai, Hadas Zehavi, Meirav Technion Israel Inst Technol Dept Comp Sci IL-3200003 Haifa Israel

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.

关键词： parameterized algorithm Weighted graph problem Vertex cover 3-Hitting set Edge dominating set

来源：评论

学校读者我要写书评

暂无评论

The label cut problem with respect to path length and label frequency

引用

THEORETICAL COMPUTER SCIENCE 2016年第0期648卷 72-83页

作者： Zhang, Peng Fu, Bin Shandong Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Univ Texas Pan Amer Dept Comp Sci Edinburg TX 78539 USA

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.

关键词： Label s-t Cut Global Label Cut parameterized algorithm Approximation algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：