The greedy coloring is a bad probabilistic algorithm
From MaRDI portal
Publication:3988828
DOI10.1016/0196-6774(91)90040-6zbMath0753.68049OpenAlexW2153584512MaRDI QIDQ3988828
Publication date: 28 June 1992
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(91)90040-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (10)
Hard graphs for randomized subgraph exclusion algorithms ⋮ Expected complexity of graph partitioning problems ⋮ An improved algorithm for approximating the chromatic number of \(G_{n,p}\) ⋮ Fast heuristics for the frequency channel assignment problem in multi-hop wireless networks ⋮ Vertex coloring of a graph for memory constrained scenarios ⋮ A passage time for greedy‐coloring cycles ⋮ Coloring k-colorable graphs in constant expected parallel time ⋮ Qos-aware service evaluation and selection ⋮ On percolation and ‐hardness ⋮ Approximating the minimum independent dominating set in perturbed graphs
This page was built for publication: The greedy coloring is a bad probabilistic algorithm
