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

Finding Optimal Triangulations parameterized by Edge Clique Cover

ALGORITHMICA 2022年第8期84卷 2242-2270页

作者： Korhonen, Tuukka Univ Helsinki Dept Comp Sci Helsinki Finland

We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover (cc) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., in the perfect phylogeny problem cc is at most the number of taxa, in fractional hypertreewidth cc is at most the number of hyperedges, and in treewidth of Bayesian networks cc is at most the number of non-root nodes. We show that the number of minimal separators of graphs is at most 2(cc), the number of potential maximal cliques is at most 3(cc), and these objects can be listed in times O*(2(cc)) and O*(3(cc)), respectively, even when no edge clique cover is given as input;the O*(.) notation omits factors polynomial in the input size. These enumeration algorithms imply O*(3(cc)) time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give O*(4(m)) time and O*(3(m)) time algorithms, respectively, where m is the number of hyperedges. When an edge clique cover of size cc' is given as a part of the input we give O*(2(cc')) time algorithms for treewidth, minimum fill-in, and chordal sandwich. This implies an O*(2(n)) time algorithm for perfect phylogeny, where n is the number of taxa. We also give polynomial space algorithms with time complexities O*(9(cc')) and O*(9(cc+O(log2cc))) for problems in this framework.

关键词： parameterized algorithms Potential maximal cliques Edge clique cover Treewidth Minimum fill-in Fractional hypertreewidth

来源：评论

学校读者我要写书评

暂无评论

parameterized Domination in Circle Graphs

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期54卷 45-72页

作者： Bousquet, Nicolas Goncalves, Daniel Mertzios, George B. Paul, Christophe Sau, Ignasi Thomasse, Stephan CNRS LIRMM AlGCo Project Team Montpellier France Univ Durham Sch Engn & Comp Sci Durham England UCBL CNRS ENS Lyon Lab LIPU LyonINRIA Lyon France

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely , where n=|V(G)|.

关键词： Circle graphs Domination problems parameterized complexity parameterized algorithms Dynamic programming Constrained domination

来源：评论

学校读者我要写书评

暂无评论

The parameterized Complexity of Unique Coverage and Its Variants

引用

ALGORITHMICA 2013年第3期65卷 517-544页

作者： Misra, Neeldhara Moser, Hannes Raman, Venkatesh Saurabh, Saket Sikdar, Somnath Inst Math Sci Madras 600113 Tamil Nadu India Univ Jena Jena Germany Rhein Westfal TH Aachen Aachen Germany

In this paper we study the parameterized complexity of the Unique Coverage problem, a variant of the classic Set Cover problem. This problem admits several parameterizations and we show that all, except the standard parameterization and a generalization of it, are unlikely to be fixed-parameter tractable. We use results from extremal combinatorics to obtain the best-known kernel for Unique Coverage and the well-known color-coding technique of Alon et al. (J. ACM 42(4), 844-856, 1995) to show that a weighted version of this problem is fixed-parameter tractable. Our application of color-coding uses an interesting variation of s-perfect hash families called (k,s)-hash families which were studied by Alon et al. (J. Comb. Theory Ser. A 104(1), 207-215, 2003) in the context of a class of codes called parent identifying codes (Barg et al. in SIAM J. Discrete Math. 14(3), 423-431, 2001). To the best of our knowledge, this is the first application of (k,s)-hash families outside the domain of coding theory. We prove the existence of such families of size smaller than the best-known s-perfect hash families using the probabilistic method (Alon and Spencer in The Probabilistic Method, Wiley, New York, 2000). Explicit constructions of such families of size promised by the probabilistic method is open.

关键词： parameterized algorithms Unique coverage Budgeted unique coverage Color coding Hash functions

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithmics for d-Hitting Set

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2010年第14期87卷 3157-3174页

作者： Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany

Based on the methodology we presented in earlier work on parameterized algorithms for 3-Hitting Set, we develop simple search tree-based algorithms for d-Hitting Set. We considerably improve on the bounds that were el... 详细信息

关键词： Hitting Set problems parameterized algorithms analysis of search tree algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of configuration integer programs

引用

OPERATIONS RESEARCH LETTERS 2021年第6期49卷 908-913页

作者： Knop, Dusan Koutecky, Martin Levin, Asaf Mnich, Matthias Onn, Shmuel Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic Charles Univ Prague Prague Czech Republic Technion Israel Inst Technol Haifa Israel Hamburg Univ Technol Inst Algorithms & Complex Hamburg Germany

Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems. First, we develop fast exact (exponential-time) algorithms for Configuration IP and matching hardness results. Second, we showcase the implications of these results to bin-packing and facility-location-like problems. (C) 2021 The Author(s). Published by Elsevier B.V.

关键词： parameterized algorithms Configuration IP Surfing

来源：评论

学校读者我要写书评

暂无评论

parameterized tractability of the maximum-duo preservation string mapping problem

引用

THEORETICAL COMPUTER SCIENCE 2016年第0期646卷 16-25页

作者： Beretta, Stefano Castelli, Mauro Dondi, Riccardo CNR Ist Tecnol Biomed Segrate Italy Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Milan Italy Univ Nova Lisboa NOVA IMS Lisbon Portugal Univ Bergamo Dipartimento Lettere Filosofia & Comunicaz Bergamo Italy

In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O (k(6)). (C) 2016 Elsevier B.V. All rights reserved.

关键词： Computational biology Common string partition parameterized algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

On Multiway Cut parameterized Above Lower Bounds

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2013年第1期5卷 1–11页

作者： Cygan, Marek Pilipczuk, Marcin Pilipczuk, Michal Wojtaszczyk, Jakub Onufry Univ Warsaw Inst Informat Warsaw Poland Google Inc Warsaw Poland

We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the node multiway cut problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon. Our results imply O*(4(k)) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an O*(2(k)) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.

关键词： algorithms Theory Fixed parameter tractability linear programming multiway cut parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithmics for linear arrangement problems

引用

DISCRETE APPLIED MATHEMATICS 2008年第17期156卷 3166-3177页

作者： Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany

We discuss different variants of linear arrangement problems from a parameterized perspective. More specifically, we concentrate on developing simple search tree algorithms for these problems. Despite this simplicity, the analysis of the algorithms is often rather intricate. For the newly introduced problem LINEAR ARRANGEMENT BY DELETING EDGES, we also show how to derive a small problem kernel. (C) 2008 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Linear arrangement problems

来源：评论

学校读者我要写书评

暂无评论

parameterized COMPLEXITY OF DIRECTED STEINER TREE ON SPARSE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第2期31卷 1294-1327页

作者： Jones, Mark Lokshtanov, Daniel Ramanujan, M. S. Saurabh, Saket Suchy, Ondrej Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Univ Bergen N-5020 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Czech Tech Univ Fac Informat Technol Prague 16636 Czech Republic

We study the parameterized complexity of the directed variant of the classical STEINER TREE problem on various classes of directed sparse graphs. While the parameterized complexity of STEINER TREE parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected STEINER TREE problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for DIRECTED STEINER TREE (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for DOMINATING SET on sparse undirected graphs. These algorithms are asymptotically optimal.

关键词： algorithms and data structures graph algorithms parameterized algorithms Steiner tree problem sparse graph classes

来源：评论

学校读者我要写书评

暂无评论

A parameterized shared-memory scheme for parameterized metaheuristics

引用

JOURNAL OF SUPERCOMPUTING 2011年第3期58卷 292-301页

作者： Almeida, Francisco Gimenez, Domingo Lopez-Espin, Jose J. Univ Murcia Dept Informat & Sistemas Murcia Spain Univ La Laguna Dept Estadist Invest Operat & Comp E-38207 San Cristobal la Laguna Spain Univ Miguel Hernandez Ctr Invest Operat Elche Spain

This paper presents a parameterized shared-memory scheme for parameterized metaheuristics. The use of a parameterized metaheuristic facilitates experimentation with different metaheuristics and hybridation/combinations to adapt them to the particular problem we are working with. Due to the large number of experiments necessary for the metaheuristic selection and tuning, parallelism should be used to reduce the execution time. To obtain parallel versions of the metaheuristics and to adapt them to the characteristics of the parallel system, a unified parameterized shared-memory scheme is developed. Given a particular computational system and fixed parameters for the sequential metaheuristic, the appropriate selection of parameters in the unified parallel scheme eases the development of parallel efficient metaheuristics.

关键词： Parallel metaheuristics Shared-memory parameterized algorithms algorithms optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：