An exact approach for the vertex coloring problem
From MaRDI portal
Publication:429677
DOI10.1016/J.DISOPT.2010.07.005zbMATH Open1244.05092OpenAlexW2035072380MaRDI QIDQ429677FDOQ429677
Authors: 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
Recommendations
- A metaheuristic approach for the vertex coloring problem
- An improved DSATUR-based branch-and-bound algorithm for the vertex coloring problem
- A survey on vertex coloring problems
- Exact solution of graph coloring problems via constraint programming and column generation
- Exact weighted vertex coloring via branch-and-price
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- A cutting plane algorithm for graph coloring
- A branch-and-cut algorithm for graph coloring
- A survey on vertex coloring problems
- A graph coloring algorithm for large scheduling problems
- Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
- New methods to color the vertices of a graph
- Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
- Hybrid evolutionary algorithms for graph coloring
- A graph coloring heuristic using partial solutions and a reactive tabu scheme
- A Column Generation Approach for Graph Coloring
- Title not available (Why is that?)
- Using tabu search techniques for graph coloring
- A Heuristic Method for the Set Covering Problem
- Title not available (Why is that?)
- An introduction to timetabling
- Using extra dual cuts to accelerate column generation
- A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
- Title not available (Why is that?)
- An adaptive memory algorithm for the \(k\)-coloring problem
- A metaheuristic approach for the vertex coloring problem
- Finding the chromatic number by means of critical graphs
- Chromatic Scheduling and the Chromatic Number Problem
- Graph colouring approaches for a satellite range scheduling problem
- Simple ingredients leading to very efficient heuristics for the maximum clique problem
- Ant local search and its efficient adaptation to graph colouring
- Title not available (Why is that?)
Cited In (57)
- Solving the list coloring problem through a branch-and-price algorithm
- Ejection chain moves for automatic neighborhood synthesis in constrained cardinality‐minimization problems
- A memetic algorithm with adaptive operator selection for graph coloring
- Minimum sum coloring problem: upper bounds for the chromatic strength
- A branch-and-cut algorithm for the edge interdiction clique problem
- A dual ascent heuristic for obtaining a lower bound of the generalized set partitioning problem with convexity constraints
- An exact method for graph coloring
- Exact solution of graph coloring problems via constraint programming and column generation
- Projective Cutting-Planes
- A Wide Branching Strategy for the Graph Coloring Problem
- Adaptive solution prediction for combinatorial optimization
- A simple branching scheme for vertex coloring problems
- An unconstrained quadratic binary programming approach to the vertex coloring problem
- A metaheuristic approach for the vertex coloring problem
- A new branch-and-bound algorithm for the maximum weighted clique problem
- Graph coloring with decision diagrams
- Linear programming formulation of the vertex colouring problem
- A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations
- Dual inequalities for stabilized column generation revisited
- Branch-and-Cut-and-Price algorithms for the preemptive RCPSP
- An integer programming approach to b-coloring
- A branch and price algorithm for list coloring problem
- A polyhedral study of the maximum stable set problem with weights on vertex-subsets
- Models and algorithms for reliability-oriented dial-a-ride with autonomous electric vehicles
- Solving vertex coloring problems as maximum weight stable set problems
- Vehicle Sequencing at Transshipment Terminals with Handover Relations
- Vertex coloring of a graph for memory constrained scenarios
- Exact algorithms for a discrete metric labeling problem
- Exact weighted vertex coloring via branch-and-price
- A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems
- An exact algorithm for the partition coloring problem
- The vertex coloring problem and its generalizations
- Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks
- Lower bounding techniques for DSATUR-based branch and bound
- A new \textsf{DSATUR}-based algorithm for exact vertex coloring
- The maximum-impact coloring polytope
- Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments
- Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
- An exact algorithm with learning for the graph coloring problem
- Graph Coloring Lower Bounds from Decision Diagrams
- Total coloring and total matching: polyhedra and facets
- Constraint and Satisfiability Reasoning for Graph Coloring
- Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
- Simple decentralized graph coloring
- Maximum-weight stable sets and safe lower bounds for graph coloring
- Safe lower bounds for graph coloring
- The minimum chromatic violation problem: a polyhedral approach
- A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques
- Title not available (Why is that?)
- A survey on vertex coloring problems
- A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph
- On the asymmetric representatives formulation for the vertex coloring problem
- Graph coloring-based approach for railway station design analysis and capacity determination
- Symmetry-breaking inequalities for ILP with structured sub-symmetry
- A branch-and-price algorithm for the minimum sum coloring problem
- Bin packing problem with conflicts and item fragmentation
- Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
This page was built for publication: An exact approach for the vertex coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429677)
