EUVIMEDEUVIMED entdecken
Crossref

A branch-and-price based heuristic for the Vertex Separator Problem

EMANUEL FLORENTIN OLARIU, CRISTIAN FRĂSINARU, SERGIU AMIHĂESEI

Carpathian Journal of Mathematics · 12.05.2026 · 42 (3) · 625-634

DOI: 10.37193/cjm.2026.03.09 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Carpathian Journal of Mathematics, online erschienen am 09.05.2026. Verfasst von EMANUEL FLORENTIN OLARIU und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For a given graph, a vertex separator is a subset of the vertex set of a graph whose removal disconnects the graph. If the graph has n vertices and b is a positive integer number, then the Vertex Separator Problem (VSP) asks to find a minimum cardinality vertex separator such that the remaining vertices can be partitioned in two edge-disconnected classes of cardinality at most b. In this paper we introduce a new integer linear programming (ILP) model for VSP which is based on a very large number of variables and present an heuristic based on the corresponding branch-and-price algorithm. One of the advantages of our formulation is the simplicity of the resulting subproblems. The numerical experiments proved to be veryencouraging: evenafter truncating our algorithm to one hour run, from 62 tested instances we got better results for 10 instances and for 33 instances we get the same results as the state-of-the-art approaches.

Zitieren

APA

OLARIU, E. F., FRĂSINARU, C., & AMIHĂESEI, S. (2026). A branch-and-price based heuristic for the Vertex Separator Problem. Carpathian Journal of Mathematics, 42(3), 625-634. https://doi.org/10.37193/cjm.2026.03.09

Vancouver

OLARIU EF, FRĂSINARU C, AMIHĂESEI S. A branch-and-price based heuristic for the Vertex Separator Problem. Carpathian Journal of Mathematics. 2026;42(3):625-634. doi:10.37193/cjm.2026.03.09

BibTeX
@article{OLARIU2026,
  author = {OLARIU, EMANUEL FLORENTIN and FRĂSINARU, CRISTIAN and AMIHĂESEI, SERGIU},
  title = {A branch-and-price based heuristic for the Vertex Separator Problem},
  journal = {Carpathian Journal of Mathematics},
  year = {2026},
  volume = {42},
  number = {3},
  pages = {625--634},
  doi = {10.37193/cjm.2026.03.09}
}
Kostenlos starten →