A polyhedral approach to edge coloring

DOI10.1016/0167-6377(91)90003-8zbMath0754.90062OpenAlexW2163809252WikidataQ56390700 ScholiaQ56390700MaRDI QIDQ1180838

Sungsoo Park, Nemhauser, George I.

Publication date: 27 June 1992

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90003-8

zbMATH Keywords

edge coloringNP-hardpolyhedral approach3-regular graphscovering edges by matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Solving binary cutting stock problems by column generation and branch- and-bound, Optimal multicast route packing, Consistency Cuts for Dantzig-Wolfe Reformulations, ATM VP-based network design, Total coloring and total matching: polyhedra and facets, The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks, A stabilized column generation scheme for the traveling salesman subtour problem, Densities, Matchings, and Fractional Edge-Colorings, The dynamic-demand joint replenishment problem with approximated transportation costs, Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, A comparison of two edge-coloring formulations, Separating type-I odd-cycle inequalities for a binary-encoded edge-coloring formulation, An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links, How important are branching decisions: fooling MIP solvers, Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results, Column-Generation in Integer Linear Programming, Cutting planes for branch-and-price algorithms, Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound, Min-cut clustering

Cites Work

• Unnamed Item
• Unnamed Item
• A new method of proving theorems on chromatic index
• Matching theory
• The ellipsoid method and its consequences in combinatorial optimization
• Solving matching problems with linear programming
• Pivot and Complement–A Heuristic for 0-1 Programming
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• The NP-Completeness of Edge-Coloring
• Odd Minimum Cut-Sets and b-Matchings
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Maximum matching and a polyhedron with 0,1-vertices