A Pruning Procedure for Exact Graph Coloring

DOI10.1287/IJOC.3.3.226MaRDI QIDQ4015385zbMATH OpenOpenAlexFDO

Authors Thomas J. Sager, Shi-Jen Lin

Publication date 13 January 1993

Published in ORSA Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/ijoc.3.3.226

zbMATH Keywords

branch-and-boundchromatic numbercomputational complexitygraph coloringgraph coloring algorithmNP-hardrandom graphsschedulingsearch tree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 956855
• A Column Generation Approach for Graph Coloring
• scientific article; zbMATH DE number 4006291
• A branch-and-cut algorithm for graph coloring
• A graph coloring algorithm for large scale scheduling problems

Cited in

(27)

• Combinatorial optimization in system configuration design
• A graph coloring algorithm for large scale scheduling problems
• An exact graph coloring algorithm using color exchange
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• Graph coloring with decision diagrams
• A hybrid approach for exact coloring of massive graphs
• A cutting plane algorithm for graph coloring
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Another look at graph coloring via propositional satisfiability
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• An exact method for graph coloring
• A branch-and-cut algorithm for graph coloring
• Solving the minimum-weighted coloring problem
• scientific article; zbMATH DE number 1728544 (Why is no real title available?)
• Exact solution of graph coloring problems via constraint programming and column generation
• An extraction and expansion approach for graph coloring
• Bounding vertex coloring by truncatedmultistage branch and bound
• An exact algorithm with learning for the graph coloring problem
• Graph k-colorability using a threshold accepting and Davis-Putnam hybrid algorithm
• scientific article; zbMATH DE number 4006291 (Why is no real title available?)
• Quantum annealing of the graph coloring problem
• Iterative coloring extension of a maximum clique
• Three algorithms for graph locally harmonious colouring
• Constraint and satisfiability reasoning for graph coloring
• scientific article; zbMATH DE number 956855 (Why is no real title available?)
• Constraint propagation in graph coloring
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022

This page was built for publication: A Pruning Procedure for Exact Graph Coloring

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