Solving NP-hard semirandom graph problems in polynomial expected time

DOI10.1016/J.JALGOR.2004.07.003MaRDI QIDQ3437092zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 1929938
• The solution of some random NP-hard problems in polynomial expected time
• Heuristics for semirandom graph problems
• On the tractability of coloring semirandom graphs
• scientific article; zbMATH DE number 1962838
• scientific article; zbMATH DE number 3985277
• Random pseudo-polynomial algorithms for exact matroid problems
• Automata, Languages and Programming
• Randomized Algorithms for Semi-Infinite Programming Problems

Cited in

(7)

• scientific article; zbMATH DE number 2019631 (Why is no real title available?)
• Towards a polynomial-time randomized algorithm for closed product-form networks
• scientific article; zbMATH DE number 1929938 (Why is no real title available?)
• Colouring Semirandom Graphs
• A generalization of Nemhauser and Trotter's local optimization theorem
• Finding planted cliques using gradient descent
• Exact recovery of planted cliques in semi-random graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3437092)