scientific article; zbMATH DE number 1107723

zbMATH Open0889.05069MaRDI QIDQ4373671FDOQ4373671

Authors: Paola Campadelli, Roberto Posenato, Alberto Bertoni 

Publication date: 11 June 1998

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

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

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)

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)