Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem
Mathematica Pannonica · 2021
DOI: 10.1556/314.2020.00005 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematica Pannonica, 2021. Verfasst von Ákos Beke und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Many combinatorial optimization problems can be expressed in terms of zero-one linear programs. For the maximum clique problem the so-called edge reformulation is applied most commonly. Two less frequently used LP equivalents are the independent set and edge covering set reformulations. The number of the constraints (as a function of the number of vertices of the ground graph) is asymptotically quadratic in the edge and the edge covering set LP reformulations and it is exponential in the independent set reformulation, respectively. F. D. Croce and R. Tadei proposed an approach in which the number of the constraints is equal to the number of the vertices. In this paper we are looking for possible tighter variants of these linear programs.
Zitieren
APA
Beke, Á., Szabó, S., & Zavalnij, B. (2021). Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem. Mathematica Pannonica. https://doi.org/10.1556/314.2020.00005
Vancouver
Beke Á, Szabó S, Zavalnij B. Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem. Mathematica Pannonica. 2021. doi:10.1556/314.2020.00005
BibTeX
@article{Beke2021,
author = {Beke, Ákos and Szabó, Sándor and Zavalnij, Bogdán},
title = {Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem},
journal = {Mathematica Pannonica},
year = {2021},
doi = {10.1556/314.2020.00005}
}
EUVIMED