Colouring random graphs in expected polynomial time

DOI10.1007/3-540-36494-3_43MaRDI QIDQ4418675zbMATH OpenFDO

Authors Amin Coja-Oghlan, Anusch Taraz

Publication date 11 August 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 3985277
• Mathematical Foundations of Computer Science 2005
• Colouring random graphs
• scientific article; zbMATH DE number 4101221
• Coloring random graphs -- an algorithmic perspective
• scientific article; zbMATH DE number 4134071
• Coloring sparse random graphs in polynomial average time
• Random I‐colorable graphs
• Coloring random graphs

Cited in

(34)

• A note on coloring sparse random graphs
• Expose-and-merge exploration and the chromatic number of a random graph
• Graphs with small chromatic numbers are easy to color
• A randomised heuristical algorithm for estimating the chromatic number of a graph
• Expected complexity of graph partitioning problems
• Approximating the independence number and the chromatic number in expected polynomial time
• Deciding \(k\)-colorability in expected polynomial time
• Fractionally total colouring \(G_{n,p}\)
• Approximating the independence number and the chromatic number in expected polynomial time
• Approximating the chromatic polynomial
• Randomized Δ-edge colouring via exchanges of complex colours
• The solution of some random NP-hard problems in polynomial expected time
• Short Note: A Las Vegas graph Colouring Algorithm
• scientific article; zbMATH DE number 434500 (Why is no real title available?)
• scientific article; zbMATH DE number 4213473 (Why is no real title available?)
• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• Solving NP-hard semirandom graph problems in polynomial expected time
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• scientific article; zbMATH DE number 3985277 (Why is no real title available?)
• Average-case complexity of backtrack search for coloring sparse random graphs
• Coloring Clique-free Graphs in Linear Expected Time
• A Random Recolouring Method for Graphs and Hypergraphs
• Coloring random graphs -- an algorithmic perspective
• MAX k-CUT and approximating the chromatic number of random graphs
• Fast parallel algorithms for coloring random graphs
• Exact and approximative algorithms for coloring G(n,p)
• Algorithms for Colouring Random k-colourable Graphs
• Coloring random graphs
• A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
• Expected polynomial-time randomized algorithm for graph coloring problem
• Hard problems on random graphs
• Backtrack: An O(1) expected time algorithm for the graph coloring problem
• Coloring in sublinear time
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)

This page was built for publication: Colouring random graphs in expected polynomial time

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