scientific article; zbMATH DE number 7650095
From MaRDI portal
Publication:5875482
DOI10.4230/LIPICS.APPROX-RANDOM.2019.28MaRDI QIDQ5875482FDOQ5875482
Authors: Suprovat Ghoshal, Anand Louis, Rahul Raychaudhury 
Publication date: 3 February 2023
Full work available at URL: https://arxiv.org/abs/1908.11631
Title of this publication is not available (Why is that?)
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
- Reducibility among Combinatorial Problems
- Approximate graph coloring by semidefinite programming
- Finding odd cycle transversals.
- LP can be a cure for parameterized problems
- Expander flows, geometric embeddings and graph partitioning
- Title not available (Why is that?)
- A Spectral Technique for Coloring Random 3-Colorable Graphs
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- New approximation algorithms for graph coloring
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
- Faster Parameterized Algorithms Using Linear Programming
- New approximation guarantee for chromatic number
- Optimal Long Code Test with One Free Bit
- Constant factor approximation for balanced cut in the PIE model
- Heuristics for semirandom graph problems
- Coloring Random and Semi-Random k-Colorable Graphs
- A New Algorithm for the Robust Semi-random Independent Set Problem
- Approximation algorithms for semi-random partitioning problems
- How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games
- How to Round Any CSP
- Coloring 3-Colorable Graphs with Less than n 1/5 Colors
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- New tools for graph coloring
- On the effect of randomness on planted 3-coloring models
- Finding Pseudorandom Colorings of Pseudorandom Graphs
Cited In (10)
- 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
- Improving the performance guarantee for approximate graph coloring
- Algorithmic discrepancy beyond partial coloring
- Approximation of min coloring by moderately exponential algorithms
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Title not available (Why is that?)
- Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs
- Title not available (Why is that?)
- On approximability of optimization problems related to red/blue-split graphs
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)
