| 弦图的团复盖和邻域复盖 |
| |
| 引用本文： | 吴举林.弦图的团复盖和邻域复盖[J].中国海洋大学学报(自然科学版),1991(1). |
| |
| 作者姓名： | 吴举林 |
| |
| 作者单位： | 青岛大学数学系 |
| |
| 摘 要： | 证明了弦图的团二分图是子树二分图,从而把弦图上一般形式的团复盖问题化为弦图上的对点团复盖,可以在多项式时间内求解。对强弦图上的邻域复盖问题,本文提出两条求解途径:一是化为弦图上的团复盖问题,一是化为可用组合方法求解的线性规划问题。
|
| 关 键 词： | 团复盖 邻域复盖 弦图 强弦图 全平衡二分图 |
CLIQUE COVERING AND NEIGHBORHOOD COVERING IN CHORDAL GRAPHS |
| |
| Wu Julin.CLIQUE COVERING AND NEIGHBORHOOD COVERING IN CHORDAL GRAPHS[J].Periodical of Ocean University of China,1991(1). |
| |
| Authors: | Wu Julin |
| |
| Abstract: | 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. |
| |
| Keywords: | clique covering neighborhood covering chordal graphs strongly chordal graphs totally balanced Dipartite graphs |
| 本文献已被 CNKI 等数据库收录！ |
