The facets of the polytope of modules of a graph

被引：0

作者：

Kieffer, Y ^{[1
]}

机构：

[1] Lab Leibniz, F-38031 Grenoble, France

来源：

OPERATIONS RESEARCH LETTERS | 2003年 / 31卷 / 06期

关键词：

polyhedral description; facets; modules; homogeneous sets; modular decomposition;

D O I：

10.1016/S0167-6377(03)00049-X

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

After recalling the main facts of the well-studied modular decomposition theory for graphs, we give the full description of the facets of the polytope of modules of a graph. Features of interest are that the constraints associated to facets are not associated to combinatorial objects, and depend only on the modular decomposition tree of the graph. Because of the recursive structure of that tree, we describe the facet constraints as the set of outputs of a non-deterministic algorithm. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：435 / 441

页数：7