scientific article; zbMATH DE number 753972

zbMATH Open0817.68090MaRDI QIDQ4698693FDOQ4698693

Authors: Marcus Peinado 

Publication date: 15 August 1995

Title of this publication is not available (Why is that?)

Recommendations

• Hard graphs for randomized subgraph exclusion algorithms
• scientific article; zbMATH DE number 956847
• MAX-CUT has a randomized approximation scheme in dense graphs
• On the independent set problem in random graphs

zbMATH Keywords

Boppana Halldórsson algorithmMAXCLIQUE approximation algorithm

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Cited In (4)

• Hard graphs for the maximum clique problem
• Hardness of Graph Pricing Through Generalized Max-Dicut
• An FPTAS for the hardcore model on random regular bipartite graphs
• Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE

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 Q4698693)