Numerical experiments with LP formulations of the maximum clique problem

DOI10.1007/S10100-021-00776-ZOpenAlexW3197317933MaRDI QIDQ2103941FDOQ2103941

Authors Dóra Kardos, Patrik Patassy, Sándor Szabó, Bogdán Zaválnij

Publication date 9 December 2022

Published in CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10100-021-00776-z

zbMATH Keywords

combinatorial optimizationgreedy coloringmaximum clique problemLP relaxation boundspractical solutions of NP complete problemszero-one linear programming

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• Some zero-one linear programming reformulations for the maximum clique problem
• scientific article; zbMATH DE number 956840
• Extended and discretized formulations for the maximum clique problem
• An exact algorithm for the maximum clique problem
• A branch and bound algorithm for the maximum clique problem

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 2226810 (Why is no real title available?)
• A fast algorithm for the maximum clique problem
• A multi-KP modeling for the maximum-clique problem
• Algorithm 457: finding all cliques of an undirected graph
• An exact algorithm for the maximum clique problem
• An improved branch and bound algorithm for the maximum clique problem
• Edmonds polytopes and a hierarchy of combinatorial problems
• Greedy algorithms for triangle free coloring
• Monotonic matrices and clique search in graphs
• Parameterized algorithms
• Some zero-one linear programming reformulations for the maximum clique problem
• Test case generators and computational results for the maximum clique problem

Cited in

(2)

• Concise integer linear programming formulation for clique partitioning problems
• A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem

Describes a project that uses

Uses Software

• Algorithm 457

This page was built for publication: Numerical experiments with LP formulations of the maximum clique problem

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