摘要
证明了弦图的团二分图是子树二分图,从而把弦图上一般形式的团复盖问题化为弦图上的对点团复盖,可以在多项式时间内求解。对强弦图上的邻域复盖问题,本文提出两条求解途径:一是化为弦图上的团复盖问题,一是化为可用组合方法求解的线性规划问题。
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.
关键词
图
弦图
团复盖
邻域
clique covering,neighborhood covering,chordal graphs,strongly chordal graphs,totally balanced Dipartite graphs
