An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs (Q290195): Difference between revisions

@@ Property / author @@
-Avrim L. Blum
@@ Property / author: Avrim L. Blum / rank @@
-Normal rank
@@ Property / author @@
-David R. Karger
@@ Property / author: David R. Karger / rank @@
-Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C85
@@ Property / Mathematics Subject Classification ID: 05C85 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C15
@@ Property / Mathematics Subject Classification ID: 05C15 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q25
@@ Property / Mathematics Subject Classification ID: 68Q25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W25
@@ Property / Mathematics Subject Classification ID: 68W25 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6588281
@@ Property / zbMATH DE Number: 6588281 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+graph coloring
@@ Property / zbMATH Keywords: graph coloring / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+approximation algorithms
@@ Property / zbMATH Keywords: approximation algorithms / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+analysis of algorithms
@@ Property / zbMATH Keywords: analysis of algorithms / rank @@
+Normal rank
@@ Property / author @@
+Avrim L. Blum
@@ Property / author: Avrim L. Blum / rank @@
+Normal rank
@@ Property / author @@
+David R. Karger
@@ Property / author: David R. Karger / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3337223
@@ Property / cites work: Q3337223 / rank @@
+Normal rank
@@ Property / cites work @@
+New approximation algorithms for graph coloring
@@ Property / cites work: New approximation algorithms for graph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Improved non-approximability results
@@ Property / cites work: Improved non-approximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate graph coloring by semidefinite programming
+Normal rank
@@ Property / cites work @@
+Ramsey numbers and an approximation algorithm for the vertex cover problem
+Normal rank
@@ Property / cites work @@
+Improving the performance guarantee for approximate graph coloring
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0020-0190(96)00190-1
+Normal rank
@@ Property / OpenAlex ID @@
+W1529433769
@@ Property / OpenAlex ID: W1529433769 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:290195