弦图的团复盖和邻域复盖  

CLIQUE COVERING AND NEIGHBORHOOD COVERING IN CHORDAL GRAPHS

作　　者：吴举林[1] 

机构地区：[1]青岛大学数学系

出　　处：《青岛海洋大学学报（自然科学版）》1991年第1期131-137,共7页Journal of Ocean University of Qingdao

摘　　要：证明了弦图的团二分图是子树二分图,从而把弦图上一般形式的团复盖问题化为弦图上的对点团复盖,可以在多项式时间内求解。对强弦图上的邻域复盖问题,本文提出两条求解途径:一是化为弦图上的团复盖问题,一是化为可用组合方法求解的线性规划问题。In this paper it is shown that the clique bipartite graphs of chorda] graphs are subtree bipartite graphs.Hence the genera] clique covering problem in chordal graphs can be reduced to clique covering to vertices in chordal graphs and can be solved in polynomial time.Two approaches arc given to solve the neighborhood covering problem in strongly chordal graphss.One is to reduce it to the clique covering problem.The other is to reduce it to a linear programming problem,which can be solved in polynomial time by a combinatorial method.

关 键 词：图 弦图 团复盖 邻域 

分 类 号：O157.6[理学—数学]