THREE ALGORITHMIC APPROACHES TO THE GENERAL POSITION PROBLEM
Abstract If G is a graph, then $X\subseteq V(G)$ is a general position set if for every two vertices $v,u\in X$ and every shortest $(u,v)$ -path P , no inner vertex of P lies in X . We propose three algorithms to compute a largest general position set in G : an integer linear programming algorithm, a genetic algorithm and a simulated annealing algorithm. These approaches are supported by examples from different areas of graph theory.
Authors
- Mostafa Tavakoli (ORCID: https://orcid.org/0000-0002-3315-1759)
- Sandi Klavžar (ORCID: https://orcid.org/0000-0002-1556-4744)
- Narjes Sabeghi (ORCID: https://orcid.org/0000-0002-8778-2150)
- Zahra Hamed-Labbafian (ORCID: https://orcid.org/0009-0008-7485-3176)
Institutions
- University of Maribor (SI)
- Ferdowsi University of Mashhad (IR)
Publication Details
- Journal
- Bulletin of the Australian Mathematical Society
- Published
- 2025-07-04
- DOI
- https://doi.org/10.1017/s0004972725100178
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00