EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Some Zero-One Linear Programming Reformulations for the Maximum Clique Problem

Ákos Beke, Sándor Szabó, Bogdán Zavalnij

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →