Efficient algorithms for finding critical subgraphs

DOI10.1016/J.DAM.2006.07.019MaRDI QIDQ2467361zbMATH OpenOpenAlexFDO

Authors P. Galinier, Alain Hertz, 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

chromatic numbergraph coloringcritical subgraphs

Mathematics Subject Classification ID

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

Recommendations

• Finding the chromatic number by means of critical graphs
• Finding the chromatic number by means of critical graphs
• Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs
• scientific article; zbMATH DE number 4087683
• Algorithmic bounds for the chromatic number†

Cites work

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

Cited in

(13)

• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• The maximum-impact coloring polytope
• An exact method for graph coloring
• A survey on vertex coloring problems
• Variable space search for graph coloring
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• Finding the chromatic number by means of critical graphs
• Solution techniques for the large set covering problem
• Finding even subgraphs even faster
• scientific article; zbMATH DE number 1796979 (Why is no real title available?)
• An exact algorithm with learning for the graph coloring problem
• Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Efficient algorithms for finding critical subgraphs

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