Facets of the graph coloring polytope

被引：25

作者：

Coll, P ^{[1
]}

Marenco, J ^{[1
]}

Díaz, IM ^{[1
]}

Zabala, P ^{[1
]}

机构：

[1] Univ Buenos Aires, Fac Ciencias Exactas & Nat, Dept Computac, Buenos Aires, DF, Argentina

来源：

ANNALS OF OPERATIONS RESEARCH | 2002年 / 116卷 / 1-4期

关键词：

graph coloring; integer programming; facets of polyhedra;

D O I：

10.1023/A:1021315911306

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem.

引用

页码：79 / 90

页数：12

共 21 条

[1] Aardal K., 1996, 96011 MAASTR U
[2] BALAS E, 1996, DIMACS SERIES DISCRE, V26, P11
[3] NEW METHODS TO COLOR THE VERTICES OF A GRAPH
BRELAZ, D
[J]. COMMUNICATIONS OF THE ACM, 1979, 22 (04) : 251 - 256
[4] Christof T, 1997, PORTA POLYHEDRON REP
[5] DEWERRA D, 1990, COMPUTING S, V7, P191
[6] GLOVER F, 1996, DIMACS SERIES DISCRE, V26, P285
[7] Grotschel M, 2012, Geometric algorithms and combinatorial optimization, V2
[8] HERZ A, 1987, COMPUTING, V39, P345
[9] Johnson DJ., 1996, CLIQUES COLORING SAT
[10] THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE
JOHNSON, DS
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1985, 6 (03): : 434 - 451

← 1 2 3 →