A cutting plane algorithm for graph coloring
From MaRDI portal
Publication:2467348
DOI10.1016/j.dam.2006.07.010zbMath1163.90012OpenAlexW1970686950MaRDI QIDQ2467348
Paula Zabala, Isabel Méndez-Díaz
Publication date: 21 January 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.010
Integer programming (90C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Integer programming techniques for the nurse rostering problem ⋮ A branch and price algorithm for list coloring problem ⋮ Improving lower bounds for equitable chromatic number ⋮ Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks ⋮ An exact algorithm with learning for the graph coloring problem ⋮ Simple decentralized graph coloring ⋮ A supernodal formulation of vertex colouring with applications in course timetabling ⋮ The minimum chromatic violation problem: a polyhedral study ⋮ The minimum chromatic violation problem: a polyhedral approach ⋮ An integer programming approach to b-coloring ⋮ Fractional programming formulation for the vertex coloring problem ⋮ Multi-constructor CMSA for the maximum disjoint dominating sets problem ⋮ A branch-and-cut algorithm for the minimum-adjacency vertex coloring problem ⋮ Maximum-weight stable sets and safe lower bounds for graph coloring ⋮ An exact approach for the vertex coloring problem ⋮ The maximum-impact coloring polytope ⋮ A polyhedral approach for the equitable coloring problem ⋮ Safe Lower Bounds for Graph Coloring ⋮ A mixed-integer linear programming approach for the t-row and the multi-bay facility layout problem ⋮ Ising formulations of some graph-theoretic problems in psychological research: models and methods ⋮ Polyhedral studies of vertex coloring problems: the standard formulation ⋮ A branch-and-cut procedure for the Udine course timetabling problem ⋮ A polyhedral study of the acyclic coloring problem ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring ⋮ Preprocessing and cutting planes with conflict graphs ⋮ A NEW APPROACH TO THE VERTEX COLORING PROBLEM ⋮ A polyhedral study of the acyclic coloring problem ⋮ A note on computational approaches for the antibandwidth problem ⋮ Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation ⋮ CsegGraph: a graph colouring instance generator ⋮ Three new upper bounds on the chromatic number ⋮ A cutting plane algorithm for MV portfolio selection model ⋮ Polyhedral results for the Equitable Coloring Problem ⋮ Integer linear programming formulations of the filter partitioning minimization problem ⋮ Graph coloring inequalities from all-different systems ⋮ Graph coloring with decision diagrams
Uses Software
Cites Work
- Geometric algorithms and combinatorial optimization
- A Pruning Procedure for Exact Graph Coloring
- New methods to color the vertices of a graph
- A Column Generation Approach for Graph Coloring
- The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
- On the facial structure of set packing polyhedra
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
