Maximum-weight stable sets and safe lower bounds for graph coloring

DOI10.1007/s12532-012-0042-3zbMath1267.90005OpenAlexW2103159428MaRDI QIDQ1946922

Stephan Held, William Cook, Edward C. Sewell

Publication date: 10 April 2013

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-012-0042-3

zbMATH Keywords

column generation graph coloring fractional chromatic number maximum-weight stable set safe computations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Related Items

Graph Coloring Lower Bounds from Decision Diagrams, A polyhedral study of the maximum stable set problem with weights on vertex-subsets, Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Lower bounding techniques for DSATUR-based branch and bound, Variable ordering for decision diagrams: a portfolio approach, An exact algorithm for the partition coloring problem, Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families, An exact algorithm for parallel machine scheduling with conflicts, A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, A Wide Branching Strategy for the Graph Coloring Problem, Total coloring and total matching: polyhedra and facets, Fractional programming formulation for the vertex coloring problem, Characteristics of the maximal independent set ZDD, Single machine parallel-batch scheduling under time-of-use electricity prices: new formulations and optimisation approaches, A generic exact solver for vehicle routing and related problems, A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph, Numerically Safe Lower Bounds for the Capacitated Vehicle Routing Problem, Maximum weight perfect matching problem with additional disjunctive conflict constraints, Exact solution of network flow models with strong relaxations, A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching, Primal Heuristics for Branch and Price: The Assets of Diving Methods, A branch-and-price algorithm for the minimum sum coloring problem, ILP models and column generation for the minimum sum coloring problem, Solving vertex coloring problems as maximum weight stable set problems, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, General cut-generating procedures for the stable set polytope, A new upper bound for the maximum weight clique problem, A new branch-and-bound algorithm for the maximum weighted clique problem, A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Solving bin packing problems using VRPSolver models, 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 note on selective line-graphs and partition colorings, Projective Cutting-Planes, Iterative Refinement for Linear Programming, A Fast Algorithm for Knapsack Problem with Conflict Graph, Graph coloring with decision diagrams

Uses Software

Cites Work