Efficient algorithms for finding critical subgraphs

DOI10.1016/j.dam.2006.07.019zbMath1130.05055OpenAlexW2034904496MaRDI QIDQ2467361

Alain Hertz, Philippe Galinier, Christian Desrosiers

Publication date: 21 January 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.07.019

zbMATH Keywords

graph coloringchromatic numbercritical subgraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An exact algorithm with learning for the graph coloring problem, Solution techniques for the large set covering problem, The maximum-impact coloring polytope, A survey on vertex coloring problems, Coloring graphs by iterated local search traversing feasible and infeasible solutions, Variable space search for graph coloring, Embedding a novel objective function in a two-phased local search for robust vertex coloring, An exact method for graph coloring, Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• Solution techniques for the large set covering problem
• Irreducibly inconsistent systems of linear inequalities
• The logic of constraint satisfaction
• Advances in sensitivity analysis and parametric programming
• Genetic and hybrid algorithms for graph coloring
• Hybrid evolutionary algorithms for graph coloring
• An adaptive memory algorithm for the \(k\)-coloring problem
• A survey of local search methods for graph coloring
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Tabu Search—Part I
• Tabu Search—Part II
• Finding a Useful Subset of Constraints for Analysis in an Infeasible Linear Program
• A Column Generation Approach for Graph Coloring
• Finding the chromatic number by means of critical graphs
• Chromatic Scheduling and the Chromatic Number Problem