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)

Cites Work

• An improved branch and bound algorithm for the maximum clique problem
• Algorithm 457: finding all cliques of an undirected graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Parameterized algorithms
• A fast algorithm for the maximum clique problem
• An exact algorithm for the maximum clique problem
• Edmonds polytopes and a hierarchy of combinatorial problems
• Test case generators and computational results for the maximum clique problem
• Greedy algorithms for triangle free coloring
• Title not available (Why is that?)
• Monotonic matrices and clique search in graphs
• Title not available (Why is that?)
• A multi-KP modeling for the maximum-clique problem
• Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem

Cited In (2)

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

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)