Heuristics for semirandom graph problems
type: Item
instance of: scholarly article
title: Heuristics for semirandom graph problems
zbMATH Open document ID: 1006.68103
author: Joe Kilian
author: Uriel Feige
published in: Journal of Computer and System Sciences
publication date: 2002-07-04T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1763416
zbMATH Keywords: semirandom graph
zbMATH Keywords: independent sets
zbMATH Keywords: colorings
zbMATH Keywords: bisections in graphs
describes a project that uses: DIMACS
MaRDI profile type: Publication
OpenAlex ID: W1987178221
cites work: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
cites work: A Spectral Technique for Coloring Random 3-Colorable Graphs
cites work: Approximating the independence number via the \(\vartheta\)-function
cites work: Q4705344
cites work: Q4004078
cites work: Coloring Random and Semi-Random k-Colorable Graphs
cites work: An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
cites work: Approximating maximum independent sets by excluding subgraphs
cites work: Q4714131
cites work: Lower Bounds for the Partitioning of Graphs
cites work: Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
cites work: Zero knowledge and the chromatic number
cites work: Finding and certifying a large hidden clique in a semirandom graph
cites work: Approximating the minimum bisection size (extended abstract)
cites work: Q3122905
cites work: The eigenvalues of random symmetric matrices
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: A still better performance guarantee for approximate graph coloring
cites work: Approximate graph coloring by semidefinite programming
cites work: On the Shannon capacity of a graph
cites work: Nonpolyhedral Relaxations of Graph-Bisection Problems
cites work: Q4252731
DOI: 10.1006/JCSS.2001.1773
description: scientific article; zbMATH DE number 1763416