A branch-and-cut algorithm for partition coloring

DOI10.1002/net.20365zbMath1205.05089OpenAlexW4243377619MaRDI 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 cutpartition coloringformulation by representatives

Mathematics Subject Classification ID

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

Related Items

On the minimum and maximum selective graph coloring problems in some graph classes ⋮ On some applications of the selective graph coloring problem ⋮ An exact algorithm for the partition coloring problem ⋮ A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives ⋮ A branch-and-price approach for the partition coloring problem ⋮ 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 ⋮ On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics ⋮ An improved hybrid ant-local search algorithm for the partition graph coloring problem ⋮ Integer programming formulations and efficient local search for relaxed correlation clustering ⋮ 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

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