Exact and approximative algorithms for coloring G(n,p)

DOI10.1002/RSA.20007MaRDI QIDQ4736774zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Anusch Taraz

Publication date 6 August 2004

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20007

zbMATH Keywords

approximation algorithmchromatic numbercoloringrandom graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1962838
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
• Approximating the independence number and the chromatic number in expected polynomial time
• scientific article; zbMATH DE number 219240
• Mathematical Foundations of Computer Science 2005

Cites work

• Almost all graphs with average degree 4 are 3-colorable
• Certifying unsatisfiability of random 2k-SAT formulas using approximation techniques.
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 1689045 (Why is no real title available?)
• scientific article; zbMATH DE number 1306877 (Why is no real title available?)
• scientific article; zbMATH DE number 1962840 (Why is no real title available?)
• scientific article; zbMATH DE number 1984543 (Why is no real title available?)
• scientific article; zbMATH DE number 1754601 (Why is no real title available?)

Cited in

(17)

• A note on coloring sparse random graphs
• Approximating the independence number and the chromatic number in expected polynomial time
• Parameterized and exact algorithms for class domination coloring
• A spectral technique for coloring random 3-colorable graphs (preliminary version)
• Exact Algorithms for Coloring Graphs While Avoiding Monochromatic Cycles
• scientific article; zbMATH DE number 3985277 (Why is no real title available?)
• Average-case complexity of backtrack search for coloring sparse random graphs
• scientific article; zbMATH DE number 1984543 (Why is no real title available?)
• scientific article; zbMATH DE number 2038711 (Why is no real title available?)
• A procedure for the strategic planning of locations, capacities and districting of jails: application to Chile
• Worst-case time bounds for coloring and satisfiability problems
• On-line list colouring of random graphs
• A generic framework for approximation analysis of greedy algorithms for star bicoloring
• Mathematical Foundations of Computer Science 2005
• 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}\)
• Approximation of min coloring by moderately exponential algorithms

This page was built for publication: Exact and approximative algorithms for coloring G(n,p)

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