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
|
Text
s10100-021-00776-z.pdf - Published Version Download (278kB) | Preview |
Official URL: https://doi.org/10.1007/s10100-021-00776-z
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 |
