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

On the algorithmic complexity of k-tuple total domination

DISCRETE APPLIED MATHEMATICS 2014年 174卷 81-91页

作者： Lan, James K. Chang, Gerard Jennhwa Natl Taiwan Univ Dept Math Taipei 10617 Taiwan Natl Taiwan Univ Taida Inst Math Sci Taipei 10617 Taiwan Natl Ctr Theoret Sci Taipei Off Taipei Taiwan

For a fixed positive integer k, a k-tuple total dominating set of a graph G is a set D subset of V (G) such that every vertex of G is adjacent to at least k vertices in D. The k-tuple total domination problem is to determine a minimum k-tuple total dominating set of G. This paper studies k-tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the k-tuple total domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph, which include trees, block graphs, cacti and block-cactus graphs. We also establish NP-hardness of the k-tuple total domination problem in undirected path graphs. (C) 2014 Elsevier B.V. All rights reserved.

关键词： k-tuple total domination Total domination Block graph Cactus Algorithm NP-complete undirected path graph

来源：评论

学校读者我要写书评

暂无评论

Computing a minimum outer-connected dominating set for the class of chordal graphs

引用

INFORMATION PROCESSING LETTERS 2013年第14-16期113卷 552-561页

作者： Keil, J. Mark Pradhan, D. Univ Saskatchewan Dept Comp Sci Saskatoon SK S7N 5C9 Canada

For a graph G = (V, E), a dominating set is a set D subset of V such that every vertex v is an element of V\D has a neighbor in D. Given a graph G = (V, E) and a positive integer k, the minimum outer-connected dominating set problem for G is to decide whether G has a dominating set D of cardinality at most k such that G[V\D] , the induced subgraph by G on V\D, is connected. In this paper, we consider the complexity of the minimum outer-connected dominating set problem for the class of chordal graphs. In particular, we show that the minimum outer-connected dominating set problem is NP-complete for doubly chordal graphs and undirected path graphs, two well studied subclasses of chordal graphs. We also give a linear time algorithm for computing a minimum outer-connected dominating set in proper interval graphs. Notice that proper interval graphs form a subclass of undirected path graphs as well as doubly chordal graphs. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.

关键词： graph algorithms Domination Outer-connected domination Proper interval graph Doubly chordal graph undirected path graph NP-complete

来源：评论

学校读者我要写书评

暂无评论

Complexity of distance paired-domination problem in graphs

引用

THEORETICAL COMPUTER SCIENCE 2012年 459卷 89-99页

作者： Chang, Gerard J. Panda, B. S. Pradhan, D. Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Natl Taiwan Univ Dept Math Taipei 10617 Taiwan Natl Taiwan Univ Taida Inst Math Sci Taipei 10617 Taiwan Natl Ctr Theoret Sci Taipei Off Taipei Taiwan Indian Inst Technol Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph G[D] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.

关键词： Distance k-dominating set Distance k-paired-dominating set Strongly chordal graph undirected path graph NP-complete Approximation algorithm APX-complete

来源：评论

学校读者我要写书评

暂无评论

Algorithmic aspects of the generalized clique-transversal problem on chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 1996年第3期66卷 189-203页

作者： Chang, MS Chen, YH Chang, GJ Yan, JH NATL CHIAO TUNG UNIV DEPT MATH APPLHSINCHU 30050TAIWAN NATL CHUNG CHENG UNIV DEPT COMP SCI & INFORMAT ENGNCHIAYI 621TAIWAN

Suppose G=(V,E) is a graph in which each maximal clique C-i is associated with an integer r(i), where 0 less than or equal to r(i) less than or equal to\C-i\. The generalized clique transversal problem is to determine the minimum cardinality of a subset D of V such that \D boolean AND C-i\greater than or equal to r(i) for every maximal clique C-i of G. The problem includes the clique-transversal problem, the i,1 clique-cover problem, and for perfect graphs, the maximum q-colorable subgraph problems as special cases. This paper gives complexity results for the problem on subclasses of chordal graphs, e.g., strongly chordal graphs, k-trees, split graphs, and undirected path graphs.

关键词： clique-transversal set neighborhood number domination dual chordal graph strongly chordal graph k-tree split graph undirected path graph

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON THE HAMILTONIAN CIRCUIT PROBLEM ON DIRECTED path graphS

引用

INFORMATION PROCESSING LETTERS 1989年第4期32卷 167-170页

作者： NARASIMHAN, G Comp. Sci. Dep. Univ. Wisconsin 1210 W. Dayton St. Madison WI 53706 USA

Bertossi and Bonuccelli (1986) proved that the Hamiltonian Circuit Problem is NP-complete even when the inputs are restricted to the special class of undirected path graphs. The corresponding problem on directed path graphs was left as an open problem. We use a characterization of directed path graphs due to Monma and Wei (1986) to prove that the Hamiltonian Circuit Problem and the Hamiltonian path Problem are NP-complete on directed path graphs.

关键词： Hamiltonian circuit intersection graph undirected path graph directed path graph NP-completeness Hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

HAMILTONIAN CIRCUITS IN INTERVAL graph GENERALIZATIONS

引用

INFORMATION PROCESSING LETTERS 1986年第4期23卷 195-200页

作者： BERTOSSI, AA BONUCCELLI, MA Dipartimento di Informatica Università di Pisa Corso Italia 40 56100 Pisa Italy

We consider the problem of finding a Hamiltonian circuit in some classes of intersection graphs which generalize interval graphs. We show that the problem is NP-complete for undirected path graphs (and hence chordal g... 详细信息

关键词： Hamiltonian circuit intersection graph interval graph undirected path graph chordal graph double interval graph rectangle graph NP-completeness

来源：评论

学校读者我要写书评

暂无评论

DOMINATING SETS IN CHORDAL graphS

引用

SIAM JOURNAL ON COMPUTING 1982年第1期11卷 191-199页

作者： BOOTH, KS JOHNSON, JH

A set of vertices D is a dominating set for a graph if every vertex is either in D or adjacent to a vertex which is in D. We show that the problem of finding a minimum dominating set in a chordal graph is NP-complete, even when restricted to undirected path graphs, but exhibit a linear time greedy algorithm for the problem further restricted to directed path graphs. Streamlined to handle only trees, our algorithm becomes the algorithm of Cockayne, Goodman and Hedetniemi. An interesting parallel with graph isomorphism is pointed out.

关键词： chordal graph directed path graph dominating set graph isomorphism interval graph minimum dominating set undirected path graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：