A branch-and-cut algorithm for partition coloring

DOI10.1002/net.20365zbMath1205.05089MaRDI QIDQ3057147

Thiago F. Noronha, Yuri Frota, Celso Carneiro Ribeiro, Nelson F. Maculan

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

zbMATH Keywords

branch and cut; partition coloring; formulation by representatives

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics, On the minimum and maximum selective graph coloring problems in some graph classes, A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives, An improved hybrid ant-local search algorithm for the partition graph coloring problem, An exact algorithm for the partition coloring problem, A branch-and-price approach for the partition coloring problem, A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph, On some applications of the selective graph coloring problem, A Branch-and-Cut Algorithm for Equitable Coloring based on a Formulation by Representatives

Cites Work

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