Coloring k-colorable graphs in constant expected parallel time
From MaRDI portal
Publication:6143974
DOI10.1007/3-540-57899-4_50zbMath1530.05049MaRDI QIDQ6143974
Publication date: 5 January 2024
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Generalized lower bounds derived from Hastad's main lemma
- The complexity of symmetric functions in bounded-depth circuits
- Graphs with small chromatic numbers are easy to color
- Parallel computation and conflicts in memory access
- Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
- Parallel graph algorithms that are efficients on average
- The solution of some random NP-hard problems in polynomial expected time
- Average Case Complete Problems
- Almost all k-colorable graphs are easy to color
- The greedy coloring is a bad probabilistic algorithm
- On colouring random graphs
- The Complexity of Near-Optimal Graph Coloring
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- The chromatic number of random graphs
This page was built for publication: Coloring k-colorable graphs in constant expected parallel time
