On the asymmetric representatives formulation for the vertex coloring problem
From MaRDI portal
Publication:2482105
DOI10.1016/j.dam.2007.05.058zbMath1138.05020OpenAlexW2055511722MaRDI QIDQ2482105
Ricardo C. Corrêa, Manoel B. Campêlo, Victor A. Campos
Publication date: 16 April 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.058
Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (38)
A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems ⋮ A polyhedral study of the maximum stable set problem with weights on vertex-subsets ⋮ Models for a Steiner multi-ring network design problem with revenues ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables ⋮ A DSATUR-based algorithm for the equitable coloring problem ⋮ An exact algorithm for the partition coloring problem ⋮ Symmetry breaking in mixed integer linear programming formulations for blocking two-level orthogonal experimental designs ⋮ A branch‐and‐cut algorithm for the ring spur assignment problem ⋮ Facet-inducing web and antiweb inequalities for the graph coloring polytope ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ The minimum chromatic violation problem: a polyhedral study ⋮ A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph ⋮ The minimum chromatic violation problem: a polyhedral approach ⋮ An integer programming approach to b-coloring ⋮ Fractional programming formulation for the vertex coloring problem ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Connected graph partitioning with aggregated and non‐aggregated gap objective functions ⋮ Min–max optimization of node‐targeted attacks in service networks ⋮ A computational comparison of several models for the exact solution of the capacity and distance constrained plant location problem ⋮ The maximum-impact coloring polytope ⋮ A polyhedral approach for the equitable coloring problem ⋮ Chromatic Gallai identities operating on Lovász number ⋮ A survey on vertex coloring problems ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ Conference scheduling: a clustering-based approach ⋮ Solving vertex coloring problems as maximum weight stable set problems ⋮ A column generation based algorithm for the robust graph coloring problem ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ General cut-generating procedures for the stable set polytope ⋮ A branch‐and‐price approach to k‐clustering minimum biclique completion problem ⋮ Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments ⋮ Finding the root graph through minimum edge deletion ⋮ Integer programming formulations and efficient local search for relaxed correlation clustering ⋮ Polyhedral results for the Equitable Coloring Problem ⋮ Integer linear programming formulations of the filter partitioning minimization problem ⋮ Memetic collaborative approaches for finding balanced incomplete block designs ⋮ Political districting to minimize cut edges
Cites Work
This page was built for publication: On the asymmetric representatives formulation for the vertex coloring problem
