Solving NP-hard semirandom graph problems in polynomial expected time

DOI10.1016/j.jalgor.2004.07.003zbMath1115.68168OpenAlexW2012464972MaRDI QIDQ3437092

Amin Coja-Oghlan

Publication date: 14 May 2007

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.07.003

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (1)

A generalization of Nemhauser and Trotter's local optimization theorem

This page was built for publication: Solving NP-hard semirandom graph problems in polynomial expected time