scientific article; zbMATH DE number 7650095
From MaRDI portal
Publication:5875482
Recommendations
- New approximation algorithms for graph coloring
- Approximate graph coloring by semidefinite programming
- Progress (and lack thereof) for graph coloring approximation problems
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Automata, Languages and Programming
- Approximation Algorithms for Some Graph Partitioning Problems
- Approximation algorithm for coloring of dotted interval graphs
- Approximation Algorithms for Maximum Edge Coloring Problem
- Analysis of approximate algorithms for edge-coloring bipartite graphs
- Approximation results for the minimum graph coloring problem
Cites work
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- A New Algorithm for the Robust Semi-random Independent Set Problem
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Approximate graph coloring by semidefinite programming
- Approximation algorithms for semi-random partitioning problems
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Coloring Random and Semi-Random k-Colorable Graphs
- Constant factor approximation for balanced cut in the PIE model
- Expander flows, geometric embeddings and graph partitioning
- Faster parameterized algorithms using linear programming
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- Finding odd cycle transversals.
- Heuristics for semirandom graph problems
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- How to Round Any CSP
- LP can be a cure for parameterized problems
- New approximation algorithms for graph coloring
- New approximation guarantee for chromatic number
- New tools for graph coloring
- On the effect of randomness on planted 3-coloring models
- Optimal Long Code Test with One Free Bit
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Reducibility among combinatorial problems
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
Cited in
(10)- scientific article; zbMATH DE number 1947053 (Why is no real title available?)
- On approximability of optimization problems related to red/blue-split graphs
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- A generic framework for approximation analysis of greedy algorithms for star bicoloring
- Approximation of min coloring by moderately exponential algorithms
- Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- scientific article; zbMATH DE number 2086377 (Why is no real title available?)
- Improving the performance guarantee for approximate graph coloring
- Algorithmic discrepancy beyond partial coloring
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875482)
