A branch-and-cut algorithm for partition coloring

DOI10.1002/NET.20365zbMATH Open1205.05089OpenAlexW4243377619MaRDI QIDQ3057147FDOQ3057147

Authors: Y. Frota, Thiago F. Noronha, Nelson Maculan, Celso C. Ribeiro 

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20365

Recommendations

• A branch-and-price approach for the partition coloring problem
• An exact algorithm for the partition coloring problem
• Routing and wavelength assignment by partition colouring
• A branch-and-cut algorithm for graph coloring
• An ant algorithm for the partition graph coloring problem

zbMATH Keywords

branch and cutpartition coloringformulation by representatives

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Routing and wavelength assignment by partition colouring
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Set Partitioning: A survey
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• A probabilistic heuristic for a computationally difficult set covering problem
• A Column Generation Approach for Graph Coloring
• A GRASP with path-relinking for private virtual circuit routing
• Chromatic Scheduling and the Chromatic Number Problem
• Cliques, holes and the vertex coloring polytope
• Separating lifted odd-hole inequalities to solve the index selection problem
• Acyclic orientations with path constraints

Cited In (19)

• On the minimum and maximum selective graph coloring problems in some graph classes
• A simple branching scheme for vertex coloring problems
• Routing and wavelength assignment by partition colouring
• An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
• The generalized minimum branch vertices problem: properties and polyhedral analysis
• MIP formulations for induced graph optimization problems: a tutorial
• An exact algorithm for the partition coloring problem
• A subexponential algorithm for the coloured tree partition problem
• An improved hybrid ant-local search algorithm for the partition graph coloring problem
• A branch-and-price approach for the partition coloring problem
• On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics
• On some applications of the selective graph coloring problem
• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• Integer programming formulations and efficient local search for relaxed correlation clustering
• A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
• A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
• Recent Advances in Constraints
• An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study

This page was built for publication: A branch-and-cut algorithm for partition coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057147)