期刊文献+

弦图的最大权强独立集

STRONGLY INDEPENDENT SET WITH MAXIMUM WEIGHT OF A CHORDAL GRAPH
原文传递
导出
摘要 一、 引言 本文中未加说明的图论术语来自文献[1]。图G=(V,E)称为弦图,如果G的任何长度大于3的圈都有弦,或者等价地,任何长度大于3的圈都不会是G的点导出子图。本文中,子图总是指点导出子图,点子集S导出的G的子图记为G[S]。团是指完备子图,通常用它的点集来表示。如果图G的每个点v都带有点权w(v),则点子集S的权定义为S中点的权的和。 A strongly independent set of a graph G is an independent set S which intersects every maximal clique of G.This paper gives a linear time algorithm of finding a strongly independent set with maximum weight of a chordal graph.
作者 吴举林
机构地区 青岛大学
出处 《应用数学学报》 CSCD 北大核心 1991年第1期50-56,共7页 Acta Mathematicae Applicatae Sinica
  • 相关文献

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部