REAL

Numerical experiments with LP formulations of the maximum clique problem

Kardos, Dóra and Patassy, Patrik and Szabó, Sándor and Zaválnij, Bogdán (2022) Numerical experiments with LP formulations of the maximum clique problem. CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, 30. pp. 1353-1367. ISSN 1435-246X

[img]
Preview
Text
s10100-021-00776-z.pdf - Published Version

Download (278kB) | Preview

Abstract

The maximum clique problems calls for determining the size of the largest clique in a given graph. This graph problem affords a number of zero-one linear programming formulations. In this case study we deal with some of these formulations. We consider ways for tightening the formulations. We carry out numerical experiments to see the improvements the tightened formulations provide.

Item Type: Article
Additional Information: University of Szeged, Szeged, Hungary Institute of Mathematics and Informatics, University of Pecs, Pecs, Hungary Alfred Renyi Institute of Mathematics, Budapest, Hungary Export Date: 16 February 2022 Correspondence Address: Zaválnij, B.; Alfred Renyi Institute of MathematicsHungary; email: bogdan@renyi.hu Funding details: European Commission, EC Funding details: European Social Fund, ESF, EFOP-3.6.3-VEKOP16-2017-00002 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, SNN–135643 Funding details: National Research, Development and Innovation Office Funding text 1: Dóra Kardos and Patrik Patassy have been supported by the European Union, cofinanced by the European Social Fund (EFOP-3.6.3-VEKOP16-2017-00002). The research of Sándor Szabó and Bogdán Zaválnij was supported by National Research, Development and Innovation Office – NKFIH Fund No. SNN–135643.
Uncontrolled Keywords: Combinatorial optimization , Maximum clique problem , Zero-one linear programming , Greedy coloring , Practical solutions of NP complete problems , LP relaxation bounds
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 15 Jul 2025 11:03
Last Modified: 15 Jul 2025 11:03
URI: https://real.mtak.hu/id/eprint/221121

Actions (login required)

Edit Item Edit Item