The weighted independent domination problem is NP-complete for chordal graphs

Chang GJ

首页> 外文期刊>Discrete Applied Mathematics >The weighted independent domination problem is NP-complete for chordal graphs

【24h】

The weighted independent domination problem is NP-complete for chordal graphs

机译：弦图的加权独立控制问题是NP完全的

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

An independent dominating set of a graph G = (VE) is a pairwise non-adjacent subset D of V such that every vertex not in D is adjacent to at least one vertex in D. Suppose each vertex in V is associated with a weight which is a real number. The weighted independent domination problem is to find an independent domination set of minimum total weights. This paper records an unpublished result of 20 years ago that the weighted independent domination problem is NP-complete for chordal graphs. (C) 2003 Elsevier B.V. All rights reserved.

著录项

来源
《Discrete Applied Mathematics》 |2004年第3期|共2页
作者
Chang GJ;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
chordal graph; independent domination; NP-complete; weight;

机译：弦图;独立支配;NP完全;权重;

相似文献

外文文献
中文文献
专利

1. The weighted independent domination problem is NP-complete for chordal graphs [J] . Chang GJ Discrete Applied Mathematics . 2004,第1a3期

机译：弦图的加权独立控制问题是NP完全的
2. Weighted Independent k-Domination of Cactus Graphs [J] . Tina Novak, Janez ?erovnik Ars Combinatoria: An Australian-Canadian Journal of Combinatorics . 2019,第期

机译：加权独立K-统治仙人掌图
3. A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs [J] . Pandit Parthe, Kulkarni Ankur A. Discrete Applied Mathematics . 2018,第期

机译：基于线性互补性的加权独立号和图形中的独立统治数的表征
4. The weighted independent domination problem in series-parallel graphs [C] . Shun-Chieh Chang, Jia-Jie Liu, Yue-Li Wang International Computer Symposium . 2015

机译：串联平行图中的加权独立统治问题
5. Closure operations and Hamiltonian properties of independent and total domination critical graphs. [D] . Simmons, Jill. 2005

机译：独立和总支配临界图的闭合运算和哈密顿性质。
6. Posterior Circulation Acute Stroke Prognosis Early Computed Tomography Score Using Hypointense Vessels on Susceptibility Weighted Imaging Independently Predicts Outcome in Patients with Basilar Artery Occlusion [O] . S. Mundiyanapurath, M. Möhlenbruch, P. A. Ringleb, -1

机译：后循环急性中风的预后使用易感性加权成像的Hypointense血管早期计算机断层扫描评分可独立预测基底动脉闭塞患者的预后
7. The weighted independent domination problem is NP-complete for chordal graphs [O] . Chang Gerard J. 2004

机译：弦图的加权独立控制问题是NP完全的
8. New Proofs for Strongly Chordal Graphs and Chordal Bipartite Graphs. [R] . Pelsmajer, M. J., Tokaz, J., West, D. B. 2004

机译：强弦图和弦二分图的新证明。

The weighted independent domination problem is NP-complete for chordal graphs

摘要

著录项

相似文献

相关主题

期刊订阅