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

A kernelization algorithm for d-Hitting Set

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第7期76卷 524-531页

作者： Abu-Khzam, Faisal N. Lebanese Amer Univ Dept Comp Sci & Math New York NY 10115 USA

For a given parameterized problem, pi, a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of pi into an equivalent one whose size depends only on the input parameter(s). The resulting instance is called a problem kernel. In this paper, a kernelization algorithm for the 3-Hitting Set problem is presented along with a general kernelization for d-Hitting Set. For 3-Hitting Set, an arbitrary instance is reduced into an equivalent one that contains at most 5k(2) + k elements. This kernelization is an improvement over previously known methods that guarantee cubic-order kernels. Our method is used also to obtain quadratic kernels for several other problems. For a constant d >= 3, a kernelization of d-Hitting Set is achieved by a non-trivial generalization of the 3-Hitting Set method, and guarantees a kernel whose order does not exceed (2d - 1)k(d-1) + k. (C) 2009 Elsevier Inc. All rights reserved.

关键词： fixed-parameter algorithms Hitting Set Kernelization Crown decomposition Vertex cover Hypergraphs

来源：评论

学校读者我要写书评

暂无评论

Shortest odd paths in undirected graphs with conservative weight functions

引用

DISCRETE APPLIED MATHEMATICS 2024年 357卷 34-50页

作者： Juettner, Alpar Kiraly, Csaba Mendoza-Cadena, Lydia Mirabel Pap, Gyula Schlotter, Ildiko Yamaguchi, Yutaro Eotv Lorand Res Network ELKH ELKH ELTE Egervary Res Grp Budapest Hungary Eotvos Lorand Univ Dept Operat Res Budapest Hungary MTA ELTE Matroid Optimizat Res Grp Budapest Hungary HUN REN Ctr Econ & Reg Stud Budapest Hungary Budapest Univ Technol & Econ Budapest Hungary Osaka Univ Grad Sch Informat Sci & Technol Dept Informat & Phys Sci Osaka Japan

We consider the SHORTEST ODD PATH problem, where given an undirected graph G, a weight function on its edges, and two vertices s and t in G, the aim is to find an (s, t)-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SHORTEST ODD PATH problem had been open for 20 years, and was recently shown to be NP-hard. We give a polynomial-time algorithm for the special case when the weight function is conservative and the set E- of negative-weight edges forms a single tree. Our algorithm exploits the strong connection between SHORTEST ODD PATH and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edgeweighted graph. It also relies on solving an intermediary problem variant called SHORTEST PARITY-CONSTRAINED ODD PATH where for certain edges we have parity constraints on their position along the path. Also, we exhibit two FPT algorithms for solving SHORTEST ODD PATH. The first FPT algorithm is parameterized by |E-|, the number of negative edges, or more generally, by the maximum size of a matching in the subgraph of G spanned by E-, when the weight function is conservative. Our second FPT algorithm is parameterized by the treewidth of G, and the algorithm does not rely on conservativeness. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC license (http://***/licenses/by- nc/4.0/).

关键词： Shortest odd path Parity constrained odd path fixed-parameter algorithms Treewidth Monadic second-order logic

来源：评论

学校读者我要写书评

暂无评论

2K₂ vertex-set partition into nonempty parts

引用

DISCRETE MATHEMATICS 2010年第6-7期310卷 1259-1264页

作者： Cook, Kathryn Dantas, Simone Eschen, Elaine M. Faria, Luerbio de Figueiredo, Celina M. H. Klein, Sulamita Univ Fed Rio de Janeiro COPPE BR-21941 Rio De Janeiro Brazil W Virginia Univ Lane Dept CSEE Morgantown WV 26506 USA Univ Fed Fluminense IM BR-24220000 Niteroi RJ Brazil Univ Estado Rio de Janeiro FFP Rio De Janeiro Brazil Univ Fed Rio de Janeiro IM BR-21941 Rio De Janeiro Brazil

A graph is 2K(2)-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K(2)-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We establish that the 2K(2)-partition problem parameterized by minimum degree is fixed-parameter tractable. We also show that for C-4-free graphs, circular-arc graphs, spiders, P-4-sparse graphs, and bipartite graphs the 2K(2)-partition problem can be solved in polynomial time. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Computational complexity Graph algorithms Structural graph theory fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

A bounded search tree algorithm for parameterized FACE COVER

引用

JOURNAL OF DISCRETE algorithms 2008年第4期6卷 541-552页

作者： Abu-Khzam, Faisal N. Fernau, Henning Langston, Michael A. Lebanese Amer Univ Div Comp Sci & Math Beirut Lebanon Univ Trier Abt Informat FB 4 D-54286 Trier Germany Univ Tennessee Dept Comp Sci Knoxville TN 37996 USA

The parameterized complexity of the FACE COVER problem is considered. The input to this problem is a plane graph G with n vertices. The question asked is whether, for a given parameter value k, there exists a set of k or fewer faces whose boundaries collectively cover (contain) every vertex in G. Early attempts achieved run times of O*(12(k)) or worse, by reducing the problem into a special form of DOMINATING SET, namely RED-BLUE DOMINATING SET, restricted to planar graphs. Here, we consider a direct approach, where some surgical operation is performed on the graph at each branching decision. This paper builds on previous work of the authors and employs a structure theorem of Aksionov et al., with a detailed case analysis, to produce a FACE COVER algorithm that runs in O(4.6056(k) + n(2)) time. We also point to the tight connections with RED-BLUE DOMINATING SET on planar graphs via the annotated version of FACE COVER that we consider in our search tree algorithm. Hence, we get both a O(4.6056(k) + n(2)) time algorithm for solving RED-BLUE dominating SET on planar graphs and a polynomial time algorithm for producing a linear kernel for annotated face cover. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Plane graphs fixed-parameter algorithms Face cover Planar red-blue dominating set

来源：评论

学校读者我要写书评

暂无评论

The constrained shortest common supersequence problem

引用

JOURNAL OF DISCRETE algorithms 2013年 21卷 11-17页

作者： Dondi, Riccardo Univ Bergamo Dipartimento Sci Umane Soc Via Donizetti 3 I-24129 Bergamo Italy

Shortest common supersequence and longest common subsequence are two widely used measures to compare sequences in different fields, from AI planning to Bioinformatics. Inspired by recently proposed variants of these two measures, we introduce a new version of the shortest common supersequence problem, where the solution is required to satisfy a given constraint on the number of occurrences of each symbol. First, we investigate the computational and approximation complexity of the problem, then we give a 3/2-approximation algorithm. Finally, we investigate the parameterized complexity of the problem, and we present a fixed-parameter algorithm. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Shortest common supersequence Approximation algorithms Computational complexity fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Linearity of grid minors in treewidth with applications through bidimensionality

引用

COMBINATORICA 2008年第1期28卷 19-36页

作者： Demaine, Erik D. Hajiachayi, Mohammadtaghi MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

We prove that any H-minor-free graph, for a fixed graph H, of treewidth w has ail Omega(w) x Omega(w) grid graph as a minor. Thus grid ininors suffice to certify that H-minor-free graphs have large treewidth, up to constant factors. This strong relationship was previously known for the special cases of planar graphs and bounded-genus graphs, and is known not to hold for general graphs. The approach of this paper can be viewed more generally as a framework for extending combinatorial results on planar graphs to hold on H-minor-free graphs for any fixed H. Our result has many combinatorial consequences on bidimensionality theory, parameter-treewidth bounds, separator theorems, and bounded local treewidth;each of these combinatorial results has several algorithmic consequences including subexponential fixed-parameter algorithms and approximation algorithms.

关键词： fixed-parameter algorithms SINGLE-CROSSING GRAPHS BOUNDED-GENUS GRAPHS PLANAR GRAPHS APPROXIMATION algorithms DOMINATING SET TREE-WIDTH DIAMETER FAMILIES THEOREM

来源：评论

学校读者我要写书评

暂无评论

Maximum Disjoint Paths on Edge-Colored Graphs: Approximability and Tractability

引用

algorithms 2013年第1期6卷 1-11页

作者： Bonizzoni, Paola Dondi, Riccardo Pirola, Yuri Univ Milano Bicocca Dept Comp Syst & Commun Milan Italy Univ Bergamo Dept Humanities & Social Sci Via Donizzetti 3 Bergamo Italy

The problem of finding the maximum number of vertex-disjoint uni-color paths in an edge-colored graph has been recently introduced in literature, motivated by applications in social network analysis. In this paper we investigate the approximation and parameterized complexity of the problem. First, we show that, for any constant epsilon > 0, the problem is not approximable within factor c(1-epsilon), where c is the number of colors, and that the corresponding decision problem is W[1]-hard when parametrized by the number of disjoint paths. Then, we present a fixed-parameter algorithm for the problem parameterized by the number and the length of the disjoint paths.

关键词： social networks disjoint paths fixed-parameter algorithms hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

A three-string approach to the closest string problem

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第1期78卷 164-178页

作者： Chen, Zhi-Zhong Ma, Bin Wang, Lusheng Tokyo Denki Univ Dept Math Sci Hiki Saitama 3590394 Japan Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). parameterized algorithms have been then developed to solve the problem when d is small. In this paper, with a new approach (called the 3-string approach), we first design a parameterized algorithm for binary strings that runs in O (nL + nd(3).6.731(d)) time, while the previous best runs in O (nL + nd.8(d)) time. We then extend the algorithm to arbitrary alphabet sizes, obtaining an algorithm that runs in time O(nL + nd.(1.612(vertical bar Sigma vertical bar + beta(2) + beta - 2))(d)), where vertical bar Sigma vertical bar is the alphabet size and beta = alpha(2) + 1 - 2 alpha(-1) + alpha(2) with alpha = 3 root root vertical bar Sigma vertical bar - 1 + 1. This new time bound is better than the previous best for small alphabets, including the very important case where vertical bar Sigma vertical bar = 4 (i.e., the case of DNA strings). (C) 2011 Elsevier Inc. All rights reserved.

关键词： Computational biology The closest string problem fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Computational Study for Planar Connected Dominating Set Problem

Computational Study for Planar Connected Dominating Set Prob...

引用

4th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Marzban, Marjan Gu, Qian-Ping Jia, Xiaohua Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9783642174605

The connected dominating set (CDS) problem is a well studied NP-hard problem with many important applications. Dorn et al. [ESA2005, LNCS3669,pp95-106] introduce a new technique to generate 2(O)(root n) time and fixed-parameter algorithms for a number of non-local hard problems, including the CDS problem in planar graphs. The practical performance of this algorithm is yet to be evaluated. We perform a computational study for such an evaluation. The results show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical result. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space. This suggests that the branch-decomposition based algorithms can be practical for the planar CDS problem.

关键词： Branch-decomposition based algorithms CDS problem planar graphs fixed-parameter algorithms computational study

来源：评论

学校读者我要写书评

暂无评论

A Quadratic Kernel for 3-Set Packing

A Quadratic Kernel for 3-Set Packing

引用

6th International Conference on Theory and Application of Models of Computation (TAMC 09)

作者： Abu-Khzam, Faisal N. Lebanese Amer Univ Dept Math & Comp Sci Beirut Lebanon

ISBN: (纸本)9783642020162

We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces ail equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced instance is called a problem kernel. Our result improves oil previously known kernelizations and call be generalized to produce improved kernels for the r-Set Packing problem whenever r is a fixed constant. Improved kernelization for r-Dimensional-Matching can also be inferred.

关键词： fixed-parameter algorithms kernelization crown decomposition Set Packing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：