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

A parametrized algorithm for matroid branch-width

SIAM JOURNAL ON COMPUTING 2005年第2期35卷 259-277页

作者： Hlineny, P Tech Univ Ostrava VSB FEI Dept Comp Sci Ostrava 70833 Czech Republic

Branch-width is a structural parameter very closely related to tree-width, but branch-width has an immediate generalization from graphs to matroids. We present an algorithm that, for a given matroid M of bounded branch-width t which is represented over a finite field, finds a branch decomposition of M of width at most 3t in cubic time. Then we show that the branch-width of M is a uniformly fixed-parameter tractable problem. Other applications include recognition of matroid properties definable in the monadic second-order logic for bounded branch-width, and [S.-I. Oum, Approximating rank-width and clique-width quickly, in Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Springer-Verlag, Heidelberg, to appear] a cubic time approximation algorithm for graph rank-width and clique-width.

关键词： representable matroid parametrized algorithm branch-width rank-width

来源：评论

学校读者我要写书评

暂无评论

Improved Parameterized Set Splitting algorithms: A Probabilistic Approach

引用

algorithmICA 2009年第4期54卷 472-489页

作者： Chen, Jianer Lu, Songjian Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

In this paper, we study parameterized algorithms for the set splitting problem, for both weighted and unweighted versions. First, we develop a new and effective technique based on a probabilistic method that allows us to develop a simpler and more efficient deterministic kernelization algorithm for the unweighted set splitting problem. We then propose a randomized algorithm for the weighted set splitting problem that is based on a new subset partition technique and has its running time bounded by O (*)(2 (k) ), which is significantly better than that of the previous best deterministic algorithm (which only works for the simpler unweighted set splitting problem) of running time O (*)(2.65 (k) ). We also show that our algorithm can be de-randomized, which leads to a deterministic parameterized algorithm of running time O (*)(4 (k) ) for the weighted set splitting problem and gives the first proof that the problem is fixed-parameter tractable.

关键词： Set splitting Randomized algorithm Derandomization parametrized algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity of conflict-free colorings of graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期566卷 39-49页

作者： Gargano, Luisa Rescigno, Adele A. Univ Salerno Dipartimento Informat I-84084 Fisciano SA Italy

We consider conflict-free colorings of graph neighborhoods: Each vertex of the graph must be assigned a color so that for each vertex v there is at least one color appearing exactly once in the neighborhood of v. The goal is to minimize the number of used colors. We consider both the case of closed neighborhoods, when the neighborhood of a node includes the node itself, and the case of open neighborhoods when a node does not belong to its neighborhood. In this paper, we study complexity aspects of the problem. We show that the problem of conflict-free coloring of closed neighborhoods is NP-complete. Moreover, we give non-approximability results for the conflict-free coloring of open neighborhoods. From a positive point of view, both problems become tractable if parameterized by the vertex cover number or the neighborhood diversity number of the graph. We present simple algorithms which improve on existing results. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Conflict-free coloring NP-complete parametrized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：