Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation

被引：9

作者：

Lee, J

Leung, J

De Vries, S

机构：

[1] IBM Corp, Thomas J Watson Res Ctr, Dept Math Sci, Yorktown Hts, NY 10598 USA

[2] Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Hong Kong, Hong Kong, Peoples R China

[3] Tech Univ Munich, Zentrum Math, D-85747 Garching, Germany

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2005年 / 9卷 / 01期

关键词：

edge coloring; integer program; binary encoding; odd cycle; separation;

D O I：

10.1007/s10878-005-5484-3

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this note, we describe an efficient algorithm for separating a class of inequalities that includes the type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation.

引用

页码：59 / 67

页数：9

共 11 条

[1]

[Anonymous], 1993, GEOMETRIC ALGORITHMS

[2]

COPPERSMITH D, 2003, FIELDS I COMMUNICATI, P71

[3] A NEW METHOD OF PROVING THEOREMS ON CHROMATIC INDEX [J].

EHRENFEUCHT, A ;

FABER, V ;

KIERSTEAD, HA .

DISCRETE MATHEMATICS, 1984, 52 (2-3) :159-164

[4] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].

FREDMAN, ML ;

TARJAN, RE .

JOURNAL OF THE ACM, 1987, 34 (03) :596-615

[5] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[6] A COMPARISON OF 2 EDGE-COLORING FORMULATIONS [J].

LEE, J ;

LEUNG, J .

OPERATIONS RESEARCH LETTERS, 1993, 13 (04) :215-223

[7] All-different polytopes [J].

Lee, J .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2002, 6 (03) :335-352

[8]

LEE J, 1990, 9001 YALE U DEP OP R

[9] A POLYHEDRAL APPROACH TO EDGE COLORING [J].

NEMHAUSER, GL ;

PARK, S .

OPERATIONS RESEARCH LETTERS, 1991, 10 (06) :315-322

[10]

Nemhauser GL, 1988, INTEGER COMBINATORIA

← 1 2 →