LIMITATIONS OF LINEMSOL LOGIC IN MODELING OPTIMIZATION PROBLEMS IN GRAPHS

- 326158
Extended Abstracts (EA)
Download
Favorite this paper
How to cite this paper?
Abstract

This work investigates second-order monadic logic with objective linear functions (LinEMSOL) applied to the modeling of optimization problems in graphs. Their expressive capacities, tractable problem classes and the relationship with structural parameters such as tree width and click width are analyzed. A conceptual hierarchy of LinEMSOL limitations is proposed, divided into levels according to the complexity of the objective function: cardinality, arithmetic with weights, and modular or global constraints. Also discussed are the logical extensions needed to overcome these limitations.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Programme
17:50 to 19:10 on 10/06/2025
Lírio
Institutions
  • 1 UERJ - Universidade do Estado do Rio de Janeiro
Track
  • 23. TAG – Graph Theory and Related Algorithms
Keywords
Monadic Logic
Optimization in Graphs
LinEMSOL
Lógica Segunda Ordem