An exact approach for the vertex coloring problem

DOI10.1016/j.disopt.2010.07.005zbMath1244.05092OpenAlexW2035072380MaRDI QIDQ429677

Enrico Malaguti, Michele Monaci, Paolo Toth

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.07.005

zbMATH Keywords

column generation computational experiments vertex coloring branch-and-price

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations, Graph Coloring Lower Bounds from Decision Diagrams, A branch and price algorithm for list coloring problem, A polyhedral study of the maximum stable set problem with weights on vertex-subsets, Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks, Lower bounding techniques for DSATUR-based branch and bound, Branch-and-Cut-and-Price algorithms for the preemptive RCPSP, An exact algorithm with learning for the graph coloring problem, An exact algorithm for the partition coloring problem, Simple decentralized graph coloring, A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques, A Wide Branching Strategy for the Graph Coloring Problem, Minimum sum coloring problem: upper bounds for the chromatic strength, The minimum chromatic violation problem: a polyhedral approach, Total coloring and total matching: polyhedra and facets, An integer programming approach to b-coloring, Ejection chain moves for automatic neighborhood synthesis in constrained cardinality‐minimization problems, Graph coloring-based approach for railway station design analysis and capacity determination, Adaptive solution prediction for combinatorial optimization, Symmetry-breaking inequalities for ILP with structured sub-symmetry, A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph, Maximum-weight stable sets and safe lower bounds for graph coloring, The maximum-impact coloring polytope, Exact weighted vertex coloring via branch-and-price, Constraint and Satisfiability Reasoning for Graph Coloring, A branch-and-price algorithm for the minimum sum coloring problem, Safe Lower Bounds for Graph Coloring, Solving vertex coloring problems as maximum weight stable set problems, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles, A new branch-and-bound algorithm for the maximum weighted clique problem, A new \textsf{DSATUR}-based algorithm for exact vertex coloring, A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints, Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments, Bin packing problem with conflicts and item fragmentation, A branch-and-cut algorithm for the edge interdiction clique problem, Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach, Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams, Dual Inequalities for Stabilized Column Generation Revisited, A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems, Projective Cutting-Planes, Vehicle Sequencing at Transshipment Terminals with Handover Relations, Graph coloring with decision diagrams

Cites Work