Fractional programming formulation for the vertex coloring problem

DOI10.1016/J.IPL.2014.06.010MaRDI QIDQ402376zbMATH OpenOpenAlexFDO

Authors Tomomi Matsui, Noriyoshi Sukegawa, Atsushi Miyauchi

Publication date 28 August 2014

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

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

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)

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.

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

Cites work

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

Cited in

(9)

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

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)