scientific article; zbMATH DE number 1107723

MaRDI QIDQ4373671zbMATH OpenFDO

Authors Paola Campadelli, Roberto Posenato, Alberto Bertoni

Publication date 11 June 1998

zbMATH Keywords

random matrixrandom graphNP-hardupper boundmaximum cutexpectationsMAXIMUM CUT

Mathematics Subject Classification ID

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

Recommendations

• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• The solution of some random NP-hard problems in polynomial expected time
• scientific article; zbMATH DE number 2079360
• A probabilistic result for the max-cut problem on random graphs

Cited in

(6)

• MAX k‐CUT and approximating the chromatic number of random graphs
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• A probabilistic result for the max-cut problem on random graphs
• On the maximal cut in a random hypergraph
• Sparse graphs: metrics and random models
• Preface

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