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

Maximization coloring problems on graphs with few P₄

DISCRETE APPLIED MATHEMATICS 2014年第Part2期164卷 539-546页

作者： Campos, Victor Linhares-Sales, Claudia Sampaio, Rudini Maia, Ana Karolinna Univ Fed Ceara Dept Comp BR-60451760 Fortaleza Ceara Brazil INRIA UNS CNRS COATIJoint Project Team I3S Sophia Antipolis France

Given a graph G, a greedy coloring of G is a proper coloring such that, for each two colors i < j, every vertex of G colored j has a neighbor colored i. The Grundy number is the maximum number of colors in a greedy coloring of G. Zaker (2006) proved that determining the Grundy number is NP-hard even for complements of bipartite graphs. A b-coloring of G is a proper coloring such that every color class contains a vertex which is adjacent to at least one vertex in every other color class. The b-chromatic number is the maximum number of colors in a b-coloring of G. Irving and Manlove (1999) proved that determining the b-chromatic number is NP-hard. In this paper, we obtain polynomial time algorithms to determine the Grundy number and the b-chromatic number of (q, q - 4)-graphs, for every fixed q, which are the graphs such that every set of at most q vertices induces at most q - 4 distinct P4. These algorithms are fixed parameter tractable on the parameter q(G), where q(G) is the minimum q such that G is a (q, q - 4)-graph. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Greedy coloring b-coloring (q, q-4)-graphs Primeval decomposition fixed parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number 28

A polynomial time algorithm to compute quantum invariants of...

引用

28th Annual ACM-SIAM Symposium on Discrete algorithms (SODA)

作者： Maria, Clement Spreer, Jonathan Univ Queensland Brisbane Qld Australia

ISBN: (纸本)9781611974782

In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4,q is known to be #P-hard in general;using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the extremely large family of 3-manifolds with first homology group of bounded rank. Our algorithm is easy to implement and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3-manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets we are able to roughly double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4,q to be added to the short list of standard properties (such as orientability, connectedness, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation.

关键词： fixed parameter tractable algorithms Turaev-Viro invariants triangulations of 3-manifolds (integral) homology almost normal surfaces combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

Rainbow Connectivity: Hardness and Tractability

Rainbow Connectivity: Hardness and Tractability

引用

31st IARCS Annual International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

作者： Ananth, Prabhanjan Nasre, Meghana Sarpatwar, Kanthi K. Indian Inst Sci Bangalore Karnataka India Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9783939897347

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively) rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below: For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite. For every fixed odd k >= 3, it is NP-Complete to decide whether rc(G) <= k. This resolves one of the open problems posed by Chakraborty et al. [4] hardness for the even case. The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors. For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2.

关键词： Computational Complexity Rainbow Connectivity Graph Theory fixed parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

Maximization coloring problems on graphs with few P₄

Maximization coloring problems on graphs with few <i>P</i><s...

引用

6th Latin American algorithms Graphs and Optimization Symposium (LAGOS11)6th Latin American algorithms Graphs and Optimization Symposium (LAGOS11)

关键词： Greedy coloring b-coloring (q, q-4)-graphs Primeval decomposition fixed parameter tractable algorithms

来源：评论

学校读者我要写书评

暂无评论

A single exponential-time FPT algorithm for cactus contraction

引用

THEORETICAL COMPUTER SCIENCE 2023年 954卷

作者： Krithika, R. Misra, Pranabendu Tale, Prafullkumar Indian Inst Technol Palakkad Palakkad India Chennai Math Inst Chennai India Indian Inst Sci Educ & Res Pune Pune India

For a collection F of graphs, the F-CONTRACTION problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F-CONTRACTION problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F-CONTRACTION in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F-CONTRACTION where F is the set of all cactus graphs and show that we can solve it in 2O(k) center dot |V(G)|O(1) time.(c) 2023 Elsevier B.V. All rights reserved.

关键词： fixed parameter tractable algorithms Graph contraction Cactus graphs

来源：评论

学校读者我要写书评

暂无评论

A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number 17

A polynomial time algorithm to compute quantum invariants of...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Clement Maria Jonathan Spreer The University of Queensland

ISBN: (纸本)9781510836358

In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV_(4,q), using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV_(4,q) is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the extremely large family of 3-manifolds with first homology group of bounded rank. Our algorithm is easy to implement and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3-manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets we are able to roughly double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV_(4,q) to be added to the short list of standard properties (such as orientability, connectedness, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation.

关键词： fixed parameter tractable algorithms Turaev-Viro invariants Triangulations of 3-manifolds (integral) homology Almost normal surfaces Combinatorial algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：