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

parameterized complexity of finding regular induced subgraphs

JOURNAL OF DISCRETE algorithmS 2009年第2期7卷 181-190页

作者： Moser, Hannes Thilikos, Dimitrios M. Friedrich Schiller Univ Jena Inst Informat Ernst Abbe Pl 2 D-07743 Jena Germany Natl & Kapodistrian Univ Athens Dept Math GR-15784 Athens Greece

The r-Regular Induced Subgraph problem asks, given a graph G and a non-negative integer k, whether G contains an r-regular induced subgraph of size at least k, that is, an induced subgraph in which every vertex has degree exactly r. In this paper we examine its parameterization k-Size r-Regular Induced Subgraph with k as parameter and prove that it is W[1]-hard. We also examine the parameterized complexity of the dual parameterized problem, namely, the k-Almost r-Regular Graph problem, which asks for a given graph G and a non-negative integer k whether G can be made r-regular by deleting at most k vertices. For this problem, we prove the existence of a problem kernel of size O(kr(r + k)(2)). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Problem kernelization parameterized algorithm Vertex deletion problem

来源：评论

学校读者我要写书评

暂无评论

Extended dynamic subgraph statistics using h-index parameterized data structures

引用

THEORETICAL COMPUTER SCIENCE 2012年 447卷 44-52页

作者： Eppstein, David Goodrich, Michael T. Strash, Darren Trott, Lowell Univ Calif Irvine Dept Comp Sci Irvine CA 92717 USA

We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of h, the h-index of the graph. Our methods extend previous results of Eppstein and Spiro for maintaining statistics for undirected subgraphs of size three to directed subgraphs and to subgraphs of size four. For the directed case, we provide a data structure to maintain counts for all 3-vertex induced subgraphs in O(h) amortized time per update. For the undirected case, we maintain the counts of size-four subgraphs in O(h(2)) amortized time per update. These extensions enable a number of new applications in Bioinformatics and Social Networking research. (c) 2011 Elsevier B.V. All rights reserved.

关键词： parameterized algorithm Subgraph h-index Dynamic graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized Approximation for Balanced k-Median 15th

Improved Parameterized Approximation for Balanced <i>k</i>-M...

引用

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

作者： Zhang, Zhen Feng, Qilong Hunan Univ Technol & Business Sch Frontier Crossover Studies Changsha 410000 Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha 410000 Peoples R China

ISBN: (纸本)9783030926816;9783030926809

Balanced k-median is a frequently encountered problem in applications requiring balanced clustering results, which generalizes the standard k-median problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. This problem is known to be W[2]-hard if parameterized by k, implying that the existence of an FPT(k)-time exact algorithm is unlikely. In this paper, we give a (3 + epsilon)-approximation algorithm for balanced k-median that runs in FPT(k) time, improving upon the previous best approximation ratio of 7.2 + epsilon obtained in the same time. The crucial step in getting the improved ratio and our main technical contribution is a different random sampling method for selecting opened facilities.

关键词： Approximation algorithm parameterized algorithm k-median

来源：评论

学校读者我要写书评

暂无评论

parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix 34

Parameterized and Approximation Results for Scheduling with ...

引用

34th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Chen, Lin Marx, Daniel Ye, Deshi Zhang, Guochuan Univ Houston Dept Comp Sci Houston TX 77204 USA Hungarian Acad Sci MTA SZTAKI Budapest Hungary Zhejiang Univ Coll Comp Sci Hangzhou Peoples R China

ISBN: (纸本)9783959770286

We study approximation and parameterized algorithms for R vertical bar vertical bar C-max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. [2] initiated the study of approximation algorithms with respect to the rank, showing that R vertical bar vertical bar C-max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4. We continue this line of research. We prove that R vertical bar vertical bar C(max )is APX-hard even if the rank is 3, resolving an open problem in [2]. We then show that R vertical bar vertical bar C-max is FPT parameterized by the rank and the largest job processing time p(maz). This generalizes the parameterized results on P vertical bar vertical bar C-max [17] and R vertical bar vertical bar C-max with few different types of machines [15]. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.

关键词： APX-hardness parameterized algorithm Scheduling Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Deciding Circular-Arc Graph Isomorphism in parameterized Logspace 33

Deciding Circular-Arc Graph Isomorphism in Parameterized Log...

引用

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

作者： Chandoo, Maurice Leibniz Univ Hannover Theoret Comp Sci Appelstr 4 D-30167 Hannover Germany

ISBN: (纸本)9783959770019

We compute a canonical circular-arc representation for a given circular-arc (CA) graph which implies solving the isomorphism and recognition problem for this class. To accomplish this we split the class of CA graphs into uniform and non-uniform ones and employ a generalized version of the argument given by Kehler et al. (2013) that has been used to show that the subclass of Helly CA graphs can be canonized in logspace. For uniform CA graphs our approach works in logspace and in addition to that Helly CA graphs are a strict subset of uniform CA graphs. Thus our result is a generalization of the canonization result for Helly CA graphs. In the nonuniform case a specific set Omega of ambiguous vertices arises. By choosing the parameter k to be the cardinality of Omega this obstacle can be solved by brute force. This leads to an O(k + log n) space algorithm to compute a canonical representation for non-uniform and therefore all CA graphs.

关键词： graph isomorphism canonical representation parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Extended dynamic subgraph statistics using h-index parameterized data structures

Extended dynamic subgraph statistics using <i>h</i>-index pa...

引用

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

作者： Eppstein, David Goodrich, Michael T. Strash, Darren Trott, Lowell Univ Calif Irvine Dept Comp Sci Irvine CA 92717 USA

ISBN: (纸本)9783642174575

关键词： parameterized algorithm Subgraph h-index Dynamic graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Parametric duality and kernelization: Lower bounds and upper bounds on kernel size

引用

SIAM JOURNAL ON COMPUTING 2007年第4期37卷 1077-1106页

作者： Chen, Jianer Fernau, Henning Kanj, Iyad A. Xia, Ge Depaul Univ Sch CTI Chicago IL 60604 USA Univ Trier Abt Informat FB 4 D-54286 Trier Germany Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Lafayette Coll Acopian Engn Ctr Dept Comp Sci Easton PA 18042 USA

Determining whether a parameterized problem is kernelizable and has a small kernel size has recently become one of the most interesting topics of research in the area of parameterized complexity and algorithms. Theoretically, it has been proved that a parameterized problem is kernelizable if and only if it is fixed-parameter tractable. Practically, applying a data reduction algorithm to reduce an instance of a parameterized problem to an equivalent smaller instance (i.e., a kernel) has led to very efficient algorithms and now goes hand-in-hand with the design of practical algorithms for solving NP-hard problems. Well-known examples of such parameterized problems include the vertex cover problem, which is kernelizable to a kernel of size bounded by 2k, and the planar dominating set problem, which is kernelizable to a kernel of size bounded by 335k. In this paper we develop new techniques to derive upper and lower bounds on the kernel size for certain parameterized problems. In terms of our lower bound results, we show, for example, that unless P = NP, planar vertex cover does not have a problem kernel of size smaller than 4k/3, and planar independent set and planar dominating set do not have kernels of size smaller than 2k. In terms of our upper bound results, we further reduce the upper bound on the kernel size for the planar dominating set problem to 67k, improving significantly the 335k previous upper bound given by Alber, Fellows, and Niedermeier [J. ACM, 51 (2004), pp. 363-384]. This latter result is obtained by introducing a new set of reduction and coloring rules, which allows the derivation of nice combinatorial properties in the kernelized graph leading to a tighter bound on the size of the kernel. The paper also shows how this improved upper bound yields a simple and competitive algorithm for the planar dominating set problem.

关键词： parameterized algorithm planar graph dominating set vertex cover independent set kernel

来源：评论

学校读者我要写书评

暂无评论

Dividing Splittable Goods Evenly and With Limited Fragmentation

引用

algorithmICA 2020年第5期82卷 1298-1328页

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden

A splittable good provided in n pieces shall be divided as evenly as possible among m agents, where every agent can take shares from at most F pieces. We call F the fragmentation and mainly restrict attention to the cases F = 1 and F = 2. For F = 1, the max-min and min-max problems are solvable in linear time. The case F = 2 has neat formulations and structural characterizations in terms of weighted graphs. First we focus on perfectly balanced solutions. While the problem is strongly NP-hard in general, it can be solved in linear time if m = n - 1, and a solution always exists in this case, in contrast to F = 1. Moreover, the problem is fixed-parameter tractable in the parameter 2m - n. (Note that this parameter measures the number of agents above the trivial threshold m = n/2.) The structural results suggest another related problem where unsplittable items shall be assigned to subsets so as to balance the average sizes (rather than the total sizes) in these subsets. We give an approximationpreserving reduction from our original splitting problem with fragmentation F = 2 to this averaging problem, and some approximation results in cases when m is close to either n or n/2.

关键词： Fair division Weighted graph Linear-time algorithm parameterized algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

DETERMINING EDGE EXPANSION AND OTHER CONNECTIVITY MEASURES OF GRAPHS OF BOUNDED GENUS

引用

SIAM JOURNAL ON COMPUTING 2013年第3期42卷 1113-1131页

作者： Patel, Viresh Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England

In this paper, we give the first polynomial-time algorithm for determining the edge expansion for a graph of fixed orientable genus. We show that for a multigraph G with m edges and orientable genus g, the edge expansion of G can be determined in time m(O(g)). We show that the same is true for various other similar measures of edge connectivity.

关键词： sparsest cut edge expansion orientable surface genus homology parameterized algorithm

来源：评论

学校读者我要写书评

暂无评论

Resolution and linear CNF formulas: Improved (n, 3)-MAxSAT algorithms

引用

THEORETICAL COMPUTER SCIENCE 2019年 774卷 113-123页

作者： Xu, Chao Chen, Jianer Wang, Jianxin Cent S Univ Sch Informat Sci & Engn Changsha 410083 Hunan Peoples R China Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

We study techniques for solving the MAxSAT problem on instances in which the variable degree is bounded by 3. The problem is NP-hard. We show how resolution principle can be applied that converts an instance into an equivalent instance in which the CNF formula becomes a linear CNF formula. We then show how more efficient branching strategies can be applied on linear CNF formulas. As applications, we present two algorithms: one of running time O*(1.194(k)) that solves the parameterized version of the problem, and the other of running time O*(1.237(n)) that solves the optimization version of the problem, both significantly improving previous best upper bounds. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Maximum satisfiability Linear CNF formula Resolution principle parameterized algorithm Exact algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：