A branch-and-cut algorithm for partition coloring

DOI10.1002/NET.20365MaRDI QIDQ3057147zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(19)

• A branch-and-cut algorithm for the equitable coloring problem using a formulation by representatives
• A subexponential algorithm for the coloured tree partition problem
• A branch-and-cut algorithm for equitable coloring based on a formulation by representatives
• Integer programming formulations and efficient local search for relaxed correlation clustering
• The generalized minimum branch vertices problem: properties and polyhedral analysis
• An exact algorithm for the partition coloring problem
• An improved hybrid ant-local search algorithm for the partition graph 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 exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
• On some applications of the selective graph 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
• Recent Advances in Constraints
• An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs
• A branch-and-price approach for the partition coloring problem
• On the minimum and maximum selective graph coloring problems in some graph classes
• Routing and wavelength assignment by partition colouring
• The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study
• A simple branching scheme for vertex coloring problems

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)