A Pruning Procedure for Exact Graph Coloring

DOI10.1287/ijoc.3.3.226zbMath0768.68177OpenAlexW2012122180MaRDI QIDQ4015385

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

computational complexityschedulingbranch-and-boundgraph coloringrandom graphschromatic numberNP-hardsearch treegraph coloring algorithm

Mathematics Subject Classification ID

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

Related Items (11)

Bounding vertex coloring by truncatedmultistage branch and bound ⋮ Iterative coloring extension of a maximum clique ⋮ Quantum annealing of the graph coloring problem ⋮ A cutting plane algorithm for graph coloring ⋮ Coloring graphs by iterated local search traversing feasible and infeasible solutions ⋮ Solving the minimum-weighted coloring problem ⋮ 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 ⋮ Three algorithms for graph locally harmonious colouring ⋮ Combinatorial optimization in system configuration design

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