S4 separation and p-partition in all-path and detour convexities
Loading...
Date
2026
Authors
Haponenko, Vladyslav
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this work, we consider problems of S4 and p-convex partition separations with respect to the all-path and the detour convexities. We give characterizations of p-all-path convex and p-detour convex graphs. With respect to all-path convexity S2, S3, and S4 separable graphs are characterized. Also, we present necessary and sufficient conditions for two sets to be S4 separable, for both convexities. Moreover, we prove that in all-path convexity the time complexity of those problems is linear, and it is NP-hard for detour convexity. Finally, we give an algorithm for determining whether two sets in graph are S4 separable with respect to all-path convexity.
Description
Keywords
all-path convexity, graph convexity, detour convexity, convex separation, p-partition, article
Citation
Haponenko V. S4 separation and p-partition in all-path and detour convexities / V. Haponenko // TWMS Journal of Applied and Engineering Mathematics. - 2026. - Vol. 16, Issue 4. - P. 443-456. - https://jaem.isikun.edu.tr/web/index.php/current/142-vol16no4/1579-s4-separation-and-p-partition-in-all-path-and-detour-convexities