A polyhedral approach to edge coloring (Q1180838)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A polyhedral approach to edge coloring |
scientific article; zbMATH DE number 30041
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A polyhedral approach to edge coloring |
scientific article; zbMATH DE number 30041 |
Statements
A polyhedral approach to edge coloring (English)
0 references
27 June 1992
0 references
The edge coloring problem is formulated as an integer linear program of covering edges by matchings. For the NP-hard case of 3-regular graphs a linear programming relaxation with additional constraints is considered using column generation. The theory and the algorithm use the fact that the chromatic index is equal to 3 or 4. Computational experiments with randomly generated and some special graphs are presented.
0 references
polyhedral approach
0 references
edge coloring
0 references
covering edges by matchings
0 references
NP-hard
0 references
3-regular graphs
0 references
