2023/02/19 by Yefim Dinitz, Dinitz, Yefim, Solomon Eyal Shimony +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2302.09614
openalex publication_date 2023/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an undirected graph G=(V,E) and vertices s,t,w1,w2∈ V, we study finding whether there exists a simple path P from s to t such that w1,w2 ∈ P. As a sub-problem, we study the question: given an undirected graph and three of its edges, does there exist a simple cycle containing all those edges? We provide necessary and sufficient conditions for the existence of such paths and cycles, and develop efficient algorithms to solve this and related problems.