2017/02/20 by João Vinicius C. Thompson, Thompson, João Vinicius C., Loana Tito Nogueira +9
Computer Science · Mathematics · #05C85 #Advanced Graph Theory Research #Advanced Optimization Algorithms Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1702.06112
openalex publication_date 2017/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work we deal with the so-called path convexities, defined over special collections of paths. For example, the collection of the shortest paths in a graph is associated with the well-known geodesic convexity, while the collection of the induced paths is associated with the monophonic convexity; and there are many other examples. Besides reviewing the path convexities in the literature, we propose a general path convexity framework, of which most existing path convexities can be viewed as particular cases. Some benefits of the proposed framework are the systematization of the algorithmic study of related problems and the possibility of defining new convexities not yet investigated.