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

Exact and parameterized algorithms for the independent cutset problem

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 148卷

作者： Rauch, Johannes Rautenbach, Dieter Souza, Ueverton S. Ulm Univ Inst Optimizat & Operat Res Ulm Germany Univ Fed Fluminense Inst Computacao Niteroi Brazil

The INDEPENDENT CUTSET problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is NP-complete even when the input graph is planar and has maximum degree five. We first present a O & lowast;(1.4423n)time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO1-expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present FPT-time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P5-free graphs. We close by introducing the notion of alpha-domination, which generalizes key ideas of this article. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Exact algorithms parameterized algorithms Independent cutset

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for finding highly connected solution

引用

THEORETICAL COMPUTER SCIENCE 2023年 942卷 47-56页

作者： Abhinav, Ankit Bandopadhyay, Susobhan Banik, Aritra Saurabh, Saket Natl Inst Sci Educ & Res OCC Homi Bhabha Natl Inst Bhubaneswar 752050 Orissa India HBNI Inst Math Sci Chennai India

To introduce our question and the parameterization, consider the classical VERTEX COVER problem. In this problem, the input is a graph G on n vertices and a positive integer l, and the goal is to find a vertex subset S of size at most l such that G - S is an independent set. Further, we want that G[S] is highly connected. That is, G[S] should be n - k edge-connected. Clearly, the problem is NP-complete, as substituting k = n - 1, we obtain the CONNECTED VERTEX COVER problem. A simple observation also shows that the problem admits an algorithm with running time nO(k). Since the problem is polynomial-time solvable for every fixed integer k, a natural parameter is the integer k. In all the problems we consider, the parameter is k, and the goal is to find a solution S of size at most l, such that G[S] is n - k edge-connected and G - S satisfies a property. We show that this version of well-known problems such as VERTEX COVER, FEEDBACK VERTEX SET, ODD CYCLE TRANSVERSAL and MULTIWAY CUT admit an algorithm with running time f (k) middot nO(1), that is, they are FPT with the parameter k. One of our main subroutines to obtain these algorithms is an FPT algorithm for n - k edge connected STEINER SUBGRAPH, which could be of an independent interest. Finally, we also show that such an algorithm is not possible for MULTICUT.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Subset problems parameterized algorithms Connectivity

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms and kernels for almost induced matching

引用

THEORETICAL COMPUTER SCIENCE 2020年 846卷 103-113页

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

The ALMOST INDUCED MATCHING problem asks whether we can delete at most k vertices from the input graph such that each vertex in the remaining graph has a degree exactly one. This paper studies parameterized algorithms for this problem by taking the size k of the deletion set as the parameter. We give a 7k-vertex kernel and an 0*(1.74851`)-time and polynomial-space algorithm, both of which are the best-known results. The linearvertex kernel is obtained by using an extended crown decomposition and careful analysis, and the parameterized algorithm is based on a branch-and-search paradigm. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Maximum induced matching Linear kernel parameterized algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for Fixed-Order Book Drawing with Few Crossings Per Edge

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2024年第5期35卷 551-577页

作者： Huang, Jingui Chen, Jie Liu, Yunlong Xiao, Guang Wang, Jianxin Hunan Normal Univ Coll Informat Sci & Engn Hunan Prov Key Lab Intelligent Comp & Language Inf Changsha Peoples R China Hunan Xiangjiang Artificial Intelligence Acad Changsha Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China China Railway Guangzhou Grp Co Ltd Informat Technol Inst Guangzhou Peoples R China

Given ann-vertex graphGwith a fixed linear ordering ofV(G) and two integersk,b,the problemfixed-order book drawingwith few crossings per edge asks whether ornotGadmits ak-page book drawing where the maximum number of crossings per edgecan be upper bounded by the numberb. This problem was posed as an open question byBhoreet al.(J. Graph algorithms Appl.2020). In this paper, we study this problem fromthe viewpoint of parameterized complexity, in particular, we develop fixed-parametertractable algorithms for it. More specifically, we show that this problem parameterizedby both the bound numberbof crossings per edge and the vertex cover number tau of the input graph admits an algorithm with running time in (b+ 2)O(tau(3))n, and this problem parameterized by both the bound numberbof crossings per edge and the pathwidth kappa of the vertex ordering admits an algorithm with running time in (b+ 2)O(kappa(2))n. Ourresults provide a specific answer to Bhoreet al.'s question.

关键词： parameterized algorithms fixed-order book drawing pseudo edge crossings

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for weighted matching and packing problems

引用

DISCRETE OPTIMIZATION 2008年第4期5卷 748-754页

作者： Wang, Jianxin Liu, Yunlong Cent S Univ Sch Informat Sci & Engn Changsha 410083 Peoples R China

The weighted m-D MATCHING and m-SET PACKING problems (m >= 3) are usually solved through approximation algorithms. In this paper, we define the parameterized versions of these problems and study their algorithms. For the weighted m-SET PACKING problem, we develop a parameterized algorithm of running time 0(12.8(mk)n(0(1))), which is based on the recently improved color-coding technology and dynamic programming. By refining the techniques, we also develop a more efficient parameterized algorithm of running time 0(12.8((m-1)k)n(0(1))) for the weighted m-D MATCHING problem, which is a restricted version of the weighted m-SET PACKING problem. (c) 2008 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Weighted m-set packing problem Weighted m-D matching problem

来源：评论

学校读者我要写书评

暂无评论

New parameterized algorithms for the edge dominating set problem

引用

THEORETICAL COMPUTER SCIENCE 2013年 511卷 147-158页

作者： Xiao, Mingyu Kloks, Ton Poon, Sheung-Hung Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan

An edge dominating set of a graph G = (V, E) is a subset M subset of E of edges in the graph such that each edge in E M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem, we are given a graph G = (V, E) and an integer k, and we are asked to decide whether G has an edge dominating set of size at most k. In this paper, we show that the parameterized edge dominating set problem can be solved in O*(2.3147(k)) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k(3)) edges. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph algorithms parameterized algorithms Kernelization Edge dominating set

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms Using Linear Programming

引用

ACM TRANSACTIONS ON algorithms 2014年第2期11卷 1–31页

作者： Lokshtanov, Daniel Narayanaswamy, N. S. Raman, Venkatesh Ramanujan, M. S. Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India Inst Math Sci Chennai 600113 Tamil Nadu India

We investigate the parameterized complexity of VERTEX COVER parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O*(2.618(k)) algorithm for the problem. Here, k is the excess of the vertex cover size over the LP optimum, and we write O*(f(k)) for a time complexity of the form O(f(k)n(O(1))). We proceed to show that a more sophisticated branching algorithm achieves a running time of O*(2.3146(k)). Following this, using previously known as well as new reductions, we give O*(2.3146k) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION, and ALMOST 2-SAT, and O*(1.5214(k)) algorithms for KONIG VERTEX DELETION and VERTEX COVER parameterized by the size of the smallest odd cycle transversal and Konig vertex deletion set. These algorithms significantly improve the best known bounds for these problems. The most notable improvement among these is the new bound for ODD CYCLE TRANSVERSAL-this is the first algorithm that improves on the dependence on k of the seminal O*(3(k)) algorithm of Reed, Smith, and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of VERTEX COVER with at most 2k - c log k vertices. Our kernel is simpler than previously known kernels achieving the same size bound.

关键词： parameterized algorithms vertex cover

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for Minimum Fill-in

引用

ALGORITHMICA 2011年第4期61卷 817-838页

作者： Bodlaender, Hans L. Heggernes, Pinar Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

We present two parameterized algorithms for the MINIMUM FILL-IN problem, also known as CHORDAL COMPLETION: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time O(k(2)nm + 3.0793(k)), and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time O(k(2)nm + 2.35965(k)) and requires O*(1.7549(k)) space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k.

关键词： Minimum Fill-in parameterized algorithms Chordal graphs Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Exact and parameterized algorithms for MAX INTERNAL SPANNING TREE

引用

ALGORITHMICA 2013年第1期65卷 95-128页

作者： Binkele-Raible, Daniel Fernau, Henning Gaspers, Serge Liedloff, Mathieu Univ Trier FB Abt Informat 4 D-54286 Trier Germany Vienna Univ Technol Inst Informat Syst 184 3 A-1040 Vienna Austria Univ Orleans LIFO F-45067 Orleans 2 France

We consider the -hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form with ca parts per thousand currency sign2. For graphs with bounded degree, c < 2. The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of when analyzed with respect to the number of vertices. We also show that its running time is when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analysis for parameterized algorithms.

关键词： Exact exponential-time algorithms Measure and conquer parameterized algorithms Spanning tree problems Maximum internal spanning trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：