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

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 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Exact and parameterized algorithms for the Independent Cutset Problem 24th

Exact and Parameterized Algorithms for the Independent Cutse...

引用

24th International Symposium on Fundamentals of Computation Theory (FCT)

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

ISBN: (纸本)9783031435867;9783031435874

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. Such a problem is NP-complete even when the input graph is planar and has maximum degree five. In this paper, we first present a O* (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 for the problem considering 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 a-domination, which allows us to identify more fixed-parameter tractable and polynomial-time solvable cases.

关键词： exact algorithms parameterized algorithms independent cutset

来源：评论

学校读者我要写书评

暂无评论

Discriminantal subset convolution: Refining exterior-algebraic methods for parameterized algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 129卷 62-71页

作者： Brand, Cornelius Vienna Univ Technol Algorithms & Complex Grp Vienna Austria

We give a simplified account of the recent algebraic methods obtained for the longest path problem of Brand, Dell and Husfeldt (STOC'18) and Brand (ESA'19). To this end, we introduce a new kind of subset convolution, discriminantal subset convolution, which we motivate as a distillate of exterior-algebraic operations. The algorithm in the new presentation achieves the almost competitive bound of 2.619k center dot poly(n), first achieved by Fomin et al. (2016) [8], for deterministically finding paths of length k, while it allows for the same running time for the k-internal out-branching problem, improving upon Brand (ESA'19) and reproducing the state-of-the-art of Brand and Pratt (ICALP'21). (c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： parameterized algorithms Algebraic algorithms Longest path problem Extensor coding Fast subset convolution

来源：评论

学校读者我要写书评

暂无评论

k-apices of Minor-closed Graph Classes. II. parameterized algorithms

引用

ACM TRANSACTIONS ON algorithms 2022年第3期18卷 1–30页

作者： Sau, Ignasi Stamoulis, Giannos Thilikos, Dimitrios M. Univ Montpellier LIRMM CNRS Montpellier France

Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G\S belongs to G. We denote by A(k)(G) the set of all graphs that are k-apices of G. In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of A(k) (G), i.e., the minor-minimal set of graphs not belonging to A(k)(G). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2(poly(k)) . n(3) and either returns a set S certifying that G is an element of A(k) (G), or reports that G is not an element of A(k) (G). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2(poly(k)) . n(2)-time.

关键词： Graph minors parameterized algorithms graph modification problems irrelevant vertex technique flat wall theorem

来源：评论

学校读者我要写书评

暂无评论

Exact and parameterized algorithms for Restricted Subset Feedback Vertex Set in Chordal Graphs 17th

Exact and Parameterized Algorithms for Restricted Subset Fee...

引用

17th Annual Conference on Theory and Applications of Models of Computation (TAMC)

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

ISBN: (纸本)9783031203497;9783031203503

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The task is to determine whether there exists a subset S subset of V \ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP-complete even when the input graph is restricted to chordal graphs. In this paper, we show that R-SFVS in chordal graphs can be solved in time O(1.1550 vertical bar V vertical bar), significantly improving all the previous results. As a by-product, we prove that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover, we obtain a 1.2738(k)vertical bar V vertical bar(O(1))-time parameterized algorithm and an O(k(2))-kernel for R-SFVS in chordal graphs.

关键词： Subset feedback vertex set Chordal graphs Exact exponential algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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 Approximation algorithms and Lower Bounds for k-Center Clustering and Variants

引用

ALGORITHMICA 2024年第8期86卷 2557-2574页

作者： Bandyapadhyay, Sayan Friggstad, Zachary Mousavi, Ramin Portland State Univ Dept Comp Sci Portland OR USA Univ Alberta Dept Comp Sci Edmonton AB Canada

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.82, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm by Agarwal and Procopiuc [Algorithmica 2002] yields an O(n log k)+(1/epsilon)(O(2d) (k1-1/d) log k-time (1+epsilon)-approximation for Euclidean k-center, where d is the dimension. We show for a closely related problem, k-supplier, the double-exponential dependence on dimension is unavoidable if one hopes to have a sub-linear dependence on k in the exponent. We also derive similar algorithmic results to the ones by Agarwal and Procopiuc for both k-center and k-supplier. We use a relatively new tool, called Voronoi separator, which makes our algorithms and analyses substantially simpler. Furthermore we consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2(O(k) (log) (k))n(2) time 3-approximation for NUkC in general metrics, and a 2(O((k) (log) (k)/epsilon))dn time (1+epsilon)-approximation for Euclidean NUkC. The latter time bound matches the bound for k-center.

关键词： parameterized algorithms Hardness Euclidean k-center Non-uniform k-center

来源：评论

学校读者我要写书评

暂无评论

parameterized approximation algorithms for weighted vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2024年 1021卷

作者： Mandal, Soumen Misra, Pranabendu Rai, Ashutosh Saurabh, Saket IIT Delhi Dept Math New Delhi India Chennai Math Inst Chennai India Inst Math Sci Chennai India Univ Bergen Bergen Norway

A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study Weighted Vertex Cover with solution size as a parameter. Formally, in the (k, W)-Vertex Cover problem, given a graph G, an integer k, a positive rational W, and a weight function w:V(G)-> Q+, the question is whether G has a vertex cover of size at most k of weight at most W, with k being the parameter. An (a,b)-bi-criteria approximation algorithm for (k,W)-Vertex Cover either produces a vertex cover S such that |S|<= ak and w(S)<= bW, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. center dot A simple (2,2)-bi-criteria approximation algorithm for (k,W)-Vertex Cover in polynomial time by modifying the standard LP-rounding algorithm. center dot A simple exact parameterized algorithm for (k,W)-Vertex Cover running in O*(1.4656(k)) time(1). center dot A (1+epsilon,2)-approximation algorithm for (k,W)-Vertex Cover running in O*(1.4656((1-epsilon)k)) time. center dot A (1.5,1.5)-approximation algorithm for (k,W)-Vertex Cover running in O*(1.414(k)) time. center dot A (2-delta,2-delta)-approximation algorithm for (k,W)-Vertex Cover running in O*(Sigma(delta k(1-2 delta)/2 delta)(i=delta k(1-2 delta)/1+2 delta) (delta k+i delta k-2i delta 1-2 delta)) time for any delta<0.5. For example, for (1.75,1.75) and (1.9,1.9)-approximation algorithms, we get running times of O*(1.272(k)) and O*(1.151(k)) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.

关键词： Weighted vertex cover parameterized algorithms Approximation algorithms parameterized approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：