Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Empirical Analysis Of Heuristic and Approximation Algorithms for the Mutual-Visibility Problem

Created by
  • Haebom

Author

Vanja Stojanovi c, Bor Panger\v{s}i\v{c}

Outline

This paper presents an empirical analysis of the NP-complete problem of mutual visibility (MV). Previous research has focused on theoretical studies, but experimental analysis of actual behavior is lacking. This paper evaluates three algorithms: a direct random heuristic, a hypergraph-based approximation algorithm, and a genetic algorithm, by applying them to various synthetic graph datasets (including datasets with analytically known μ(G) values and general graph models). As a result, the algorithms achieve MV set sizes that are consistent with the theoretical bounds for small graphs, but significantly deviate from the theoretical bounds for large graphs. Although absolute quality assessment is difficult due to the lack of strict bounds, the genetic algorithm and other heuristic algorithms experimentally show the best performance when verified on known optimal graphs.

Takeaways, Limitations

•
Takeaways:
◦
We provide an empirical comparative analysis of the performance of three algorithms for the mutual visibility problem.
◦
On small graphs, the algorithms produce results that are consistent with theoretical bounds.
◦
We experimentally demonstrate that genetic algorithms perform the best.
•
Limitations:
◦
For large graphs, the results of the algorithm deviate significantly from the theoretical limits.
◦
The absence of strict theoretical boundaries makes it difficult to assess the absolute quality of a solution.
👍
Made with Slashpage