scientific article; zbMATH DE number 2038711

MaRDI QIDQ4449176zbMATH OpenFDO

Authors Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani

Publication date 8 February 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2719/27190200.htm

Mathematics Subject Classification ID

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) Approximation algorithms (68W25)

Recommendations

• MAX k‐CUT and approximating the chromatic number of random graphs
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
• Exact and approximative algorithms for coloring G(n,p)
• scientific article; zbMATH DE number 1962838
• Approximating the independence number and the chromatic number in expected polynomial time

Cited in

(10)

• On approximate graph colouring and MAX-k-CUT algorithms based on the -function
• scientific article; zbMATH DE number 1670810 (Why is no real title available?)
• Linear-Time Approximation Algorithms for the Max Cut Problem
• On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments
• Random MAX SAT, random MAX CUT, and their phase transitions
• MAX-CUT has a randomized approximation scheme in dense graphs
• Spectral techniques applied to sparse random graphs
• MAX k‐CUT and approximating the chromatic number of random graphs
• Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)

This page was built for publication:

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