scientific article; zbMATH DE number 753972

MaRDI QIDQ4698693zbMATH OpenFDO

Authors Marcus Peinado

Publication date 15 August 1995

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)

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

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)