A Pruning Procedure for Exact Graph Coloring
DOI10.1287/IJOC.3.3.226zbMATH Open0768.68177OpenAlexW2012122180MaRDI QIDQ4015385FDOQ4015385
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
Recommendations
computational complexitychromatic numbergraph coloringschedulingNP-hardrandom graphssearch treebranch-and-boundgraph coloring algorithm
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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)
Cited In (24)
- Coloring graphs by iterated local search traversing feasible and infeasible solutions
- An exact method for graph coloring
- Exact solution of graph coloring problems via constraint programming and column generation
- Solving the minimum-weighted coloring problem
- Bounding vertex coloring by truncatedmultistage branch and bound
- Graph coloring with decision diagrams
- Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
- An extraction and expansion approach for graph coloring
- Graph \(k\)-colorability using a threshold accepting and Davis-Putnam hybrid algorithm
- Title not available (Why is that?)
- A new \textsf{DSATUR}-based algorithm for exact vertex coloring
- Combinatorial optimization in system configuration design
- An exact algorithm with learning for the graph coloring problem
- Quantum annealing of the graph coloring problem
- A graph coloring algorithm for large scale scheduling problems
- Embedding a novel objective function in a two-phased local search for robust vertex coloring
- Iterative coloring extension of a maximum clique
- A cutting plane algorithm for graph coloring
- Another look at graph coloring via propositional satisfiability
- A branch-and-cut algorithm for graph coloring
- Title not available (Why is that?)
- Three algorithms for graph locally harmonious colouring
- Constraint propagation in graph coloring
- Constraint and satisfiability reasoning for graph coloring
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)
