Fractional programming formulation for the vertex coloring problem

DOI10.1016/J.IPL.2014.06.010zbMATH Open1358.05112arXiv1402.5769OpenAlexW2035728652MaRDI QIDQ402376FDOQ402376

Authors: Tomomi Matsui, Noriyoshi Sukegawa, Atsushi Miyauchi 

Publication date: 28 August 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We devise a new formulation for the vertex coloring problem. Different from other formulations, decision variables are associated with the pairs of vertices. Consequently, colors will be distinguishable. Although the objective function is fractional, it can be replaced by a piece-wise linear convex function. Numerical experiments show that our formulation has significantly good performance for dense graphs.

Full work available at URL: https://arxiv.org/abs/1402.5769

Recommendations

• New integer linear programming models for the vertex coloring problem
• On the asymmetric representatives formulation for the vertex coloring problem
• Linear programming formulation of the vertex colouring problem
• A parallel lagrangian heuristic for the fractional chromatic number of a graph
• Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

zbMATH Keywords

combinatorial problemsvertex coloringfractional programming formulationmixed integer linear programming problem

Mathematics Subject Classification ID

Linear programming (90C05) Fractional programming (90C32) Semidefinite programming (90C22) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• A cutting plane algorithm for graph coloring
• A branch-and-cut algorithm for graph coloring
• A survey on vertex coloring problems
• Maximum-weight stable sets and safe lower bounds for graph coloring
• On the asymmetric representatives formulation for the vertex coloring problem
• A Column Generation Approach for Graph Coloring
• Facets of the clique partitioning polytope
• A supernodal formulation of vertex colouring with applications in course timetabling
• Exact solution of graph coloring problems via constraint programming and column generation
• Cliques, holes and the vertex coloring polytope
• An unconstrained quadratic binary programming approach to the vertex coloring problem

Cited In (9)

• New integer linear programming models for the vertex coloring problem
• An unconstrained quadratic binary programming approach to the vertex coloring problem
• Linear programming formulation of the vertex colouring problem
• Polyhedral studies of vertex coloring problems: the standard formulation
• A parallel lagrangian heuristic for the fractional chromatic number of a graph
• The distance polytope for the vertex coloring problem
• An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
• Constrained integer fractional programming problem with box constraints
• A column generation based algorithm for the robust graph coloring problem

This page was built for publication: Fractional programming formulation for the vertex coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402376)