An exact method for graph coloring

DOI10.1016/J.COR.2005.01.008MaRDI QIDQ2489282zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 16 May 2006

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2005.01.008

zbMATH Keywords

Exact methodLinear decompositionLinear width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 956855
• An exact graph coloring algorithm using color exchange
• An exact approach for the vertex coloring problem
• The method of coloring in graphs and its application
• A Pruning Procedure for Exact Graph Coloring
• scientific article; zbMATH DE number 1303525
• An algorithm for coloring some perfect graphs
• A polyhedral approach for graph coloring
• Graph colouring and the probabilistic method

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906523 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 956852 (Why is no real title available?)
• scientific article; zbMATH DE number 956854 (Why is no real title available?)
• scientific article; zbMATH DE number 956855 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Pruning Procedure for Exact Graph Coloring
• A branch-and-cut algorithm for graph coloring
• A decomposition algorithm for network reliability evaluation
• An introduction to timetabling
• Complexity of Finding Embeddings in a k-Tree
• Efficient algorithms for finding critical subgraphs
• Finding the chromatic number by means of critical graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Hybrid evolutionary algorithms for graph coloring
• New methods to color the vertices of a graph
• On a multiconstrained model for chromatic scheduling
• Some sequential graph colouring algorithms
• Using tabu search techniques for graph coloring

Cited in

(12)

• A new ant colony optimization algorithm for the lower bound of sum coloring problem
• Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
• Exact solution of graph coloring problems via constraint programming and column generation
• Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• Combinatorial optimization in system configuration design
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
• Improving the extraction and expansion method for large graph coloring
• Lower bounds for the minimal sum coloring problem
• scientific article; zbMATH DE number 4006291 (Why is no real title available?)
• Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach
• An exact algorithm with learning for the graph coloring problem

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: An exact method for graph coloring

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