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

Representative Families of Product Families

ACM TRANSACTIONS ON algorithms 2017年第3期13卷 36-36页

作者： Fomin, Fedor V. Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India HBNI Inst Math Sci Theoret Comp Sci Madras 600113 Tamil Nadu India Univ Bergen Bergen Norway

A subfamily F' of a set family F is said to q-represent F if for every A is an element of F and B of size q such that A boolean AND B = empty set there exists a set A' is an element of F' such that A' boolean AND B = empty set. Recently, we provided an algorithm that, for a given family F of sets of size p together with an integer q, efficiently computes a q-representative family F' of F of size approximately (p+q/p). In this article, we consider the efficient computation of q-representative families for product families F. A family F is a product family if there exist families A and 15 such that F = {A boolean OR B : A is an element of A, B is an element of B, A boolean AND B = empty set}. Our main teclutical contribution is an algorithm that, given A, B and q, computes a q-representative family F' of F. The running time of our algorithm is sublineur in vertical bar F vertical bar for many choices of A, B, and q that occur naturally in several dynamic programming algorithms. We also give an algorithm for the computation of q-representative families for product families F in the more general setting where q-representation also involves independence in a matroid in addition to disjointness. This algorithm considerably outperforms the naive approach where one first computes F from A and B and then computes the q-representative family F' from F. We give two applications of our new algorithms for computing q-representative families for product families. The first is a 3.8408(k)n(O(1)) deterministic algorithm for the MULTILINEAR MONOMIAL DETECTION (k-MLD) problem. The second is a significant improvement of deterministic dynamic programming algorithms for "connectivity problems" on graphs of bounded treewidth.

关键词： Matroids representative families parameterized algorithms multi-linear monomial detection tree-width bounded graphs

来源：评论

学校读者我要写书评

暂无评论

Faster Exact and parameterized Algorithm for Feedback Vertex Set in Tournaments 33

Faster Exact and Parameterized Algorithm for Feedback Vertex...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kumar, Mithilesh Lokshtanov, Daniel Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783959770019

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the FEEDBACK VERTEX SET problem in tournaments. Here the input is a tournament T and an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for FEEDBACK VERTEX SET IN TOURNAMENTS. The running time of our algorithm is upper-bounded by O(1.6181(k) + n(O(1))) and by O(1.466(n)). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by Dom et al. running in time O(2(k)k(O(1)) + n(O(1))), and the fastest known exact exponential-time algorithm by Gaspers and Mnich with running time O(1.674(n)). On the way to proving our main result we prove a strengthening of a special case of a graph partitioning theorem due to Bollobas and Scott. In particular we show that the vertices of any undirected m-edge graph of maximum degree d can be colored white or black in such a way that for each of the two colors, the number of edges with both endpoints of that color is between m/4 - d/2 and m/4+d/2.

关键词： parameterized algorithms Exact algorithms Feedback vertex set Tournaments Graph partitions

来源：评论

学校读者我要写书评

暂无评论

A parameterized Algorithm for Bounded-Degree Vertex Deletion 22nd

A Parameterized Algorithm for Bounded-Degree Vertex Deletion

引用

22nd International Computing and Combinatorics Conference (COCOON)

作者： Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

ISBN: (纸本)9783319426341;9783319426334

The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the (d + 2)-hitting set problem and generates the famous vertex cover problem. The d-bounded-degree vertex deletion problem is NP-hard for each fixed d >= 0. In terms of parameterized complexity, the problem parameterized by k is W[2]-hard for unbounded d and fixed-parameter tractable for each fixed d >= 0. Previously, (randomized) parameterized algorithms for this problem with running time bound O*((d + 1)(k)) are only known for d <= 2. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in O*((d + 1)(k)) time for each d >= 3. Note that it is an open problem whether the d ' -hitting set problem can be solved in O*((d ' - 1)(k)) time for d ' >= 3. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of O*(3.0645(k)) for the case that d = 2, improving the previous deterministic bound of O*(3.24(k)).

关键词： parameterized algorithms Graph algorithms Bounded-degree vertex deletion Hitting set

来源：评论

学校读者我要写书评

暂无评论

A faster fixed parameter algorithm for two-layer crossing minimization

引用

INFORMATION PROCESSING LETTERS 2016年第9期116卷 547-549页

作者： Kobayashi, Yasuaki Tamaki, Hisao Gakushuin Univ Toshima Ku 1-5-1 Mejiro Tokyo 1718588 Japan Meiji Univ Tama Ku 1-1-1 Higashimita Kawasaki Kanagawa 2148571 Japan Kyoto Univ Sakyo Ku Kyoto 6068501 Japan

We give an algorithm that decides whether the bipartite crossing number of a given graph is at most k. The running time of the algorithm is upper bounded by 2(O(k)) + n(O(1)), where n is the number of vertices of the input graph, which improves the previously known algorithm due to Kobayashi et al. (TCS 2014) that runs in 2(O(klogk)) + n(O(1)) time. This result is based on a combinatorial upper bound on the number of two-layer drawings of a connected bipartite graph with a bounded crossing number. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Bipartite crossing number Graph algorithms Graph drawing parameterized algorithms Two-layer crossing minimization

来源：评论

学校读者我要写书评

暂无评论

Computations by fly-automata beyond monadic second-order logic

引用

THEORETICAL COMPUTER SCIENCE 2016年 619卷 32-67页

作者： Courcelle, Bruno Durand, Irene CNRS LaBRI 351 Cours Liberat F-33405 Talence France Bordeaux Univ 351 Cours Liberat F-33405 Talence France

The validity of a monadic-second order (MS) expressible property can be checked in linear time on graphs of bounded tree-width or clique-width given with appropriate decompositions. This result is proved by constructing from the MS sentence expressing the property and an integer that bounds the tree-width or clique-width of the input graph, a finite automaton intended to run bottom-up on the algebraic term representing a decomposition of the input graph. As we cannot construct practically the transition tables of these automata because they are huge, we use fly-automata whose states and transitions are computed "on the fly", only when needed for a particular input. Furthermore, we allow infinite sets of states and we equip automata with output functions. Thus, they can check properties that are not MS expressible and compute values, for example, the number of p-colorings of a graph. We obtain XP and FPT graph algorithms, parameterized by tree width or clique-width. We show how to construct easily such algorithms by combining predefined automata for basic functions and properties. These combinations reflect the structure of the MS formula that specifies the property to check or the function to compute. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Monadic second-order logic Graph algorithms Infinite automata parameterized algorithms Tree-width Clique-width Dynamic programming Model-checking Data complexity Algorithmic meta-theorems

来源：评论

学校读者我要写书评

暂无评论

Between Treewidth and Clique-Width

引用

ALGORITHMICA 2016年第1期75卷 218-253页

作者： Saether, Sigve Hortemo Telle, Jan Arne Univ Bergen Dept Informat N-5008 Bergen Norway

Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by Fomin et al. (Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 493-502, 2010a;SIAM J Comput 39(5):1941-1956, 2010b). We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of Vatshelle (New width parameters of graphs. The University of Bergen, 2012) on maximum matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by sm-width.

关键词： parameterized algorithms Width parameters of graphs Split decompositions

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for d-HITTING SET: The weighted case

引用

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1698-1713页

作者： Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany Univ Tubingen D-72074 Tubingen Germany Univ Hertfordshire Hatfield AL10 9AB Herts England

We are going to analyze search tree algorithms for WEIGHTED d-HITTING SET. Although the algorithms that we develop are fairly simple, their analysis is technically involved. We compare the weighted case with the previously analyzed unweighted one, exhibiting that the advantage of the unweighted case dwindles with growing d. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Hitting set problems parameterized algorithms Search tree algorithms

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernels for Deletion to Classes of Acyclic Digraphs 33

Polynomial Kernels for Deletion to Classes of Acyclic Digrap...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Mnich, Matthias van Leeuwen, Erik Jan Univ Bonn Bonn Germany Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9783959770019

We consider the problem to find a set X of vertices (or arcs) with vertical bar X vertical bar <= k in a given digraph G such that D = G - X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains N P-hard, but we can obtain a kernel with k(O)(1) vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.

关键词： directed feedback vertex/arc set parameterized algorithms kernels

来源：评论

学校读者我要写书评

暂无评论

Between Treewidth and Clique-Width 40

引用

40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Saether, Sigve Hortemo Telle, Jan Arne Univ Bergen Dept Informat N-5008 Bergen Norway

ISBN: (纸本)9783319123394

关键词： parameterized algorithms Width parameters of graphs Split decompositions

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms via Monotone Local Search 16

Exact Algorithms via Monotone Local Search

引用

48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Fomin, Fedor V. Gaspers, Serge Lokshtanov, Daniel Saurabh, Saket Univ Bergen Bergen Norway UNSW Australia Sydney NSW Australia CSIRO Data61 Canberra ACT Australia Inst Math Sci Madras Tamil Nadu India

ISBN: (纸本)9781450341325

We give a new general approach for designing exact exponential -time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is WEIGHTED d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W, and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search", where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c(k)n(O(1)) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2-1/c)n). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQUE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplicat

关键词： Combinatorial bounds exponential time algorithms parameterized algorithms randomized algorithms subset problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：