Title: Linear time algorithms for two disjoint paths problems on directed acyclic graphs
Abstract: We present an algorithm that, given two vertices s1 and s2 of a directed acyclic graph, constructs in linear time a data structure using linear space that, for each pair (u,v) of two vertices u and v, in constant time can output a tuple (s1,t1,s2,t2) with {t1,t2}={u,v} such that there are two disjoint paths p1, from s1 to t1, and p2, from s2 to t2, if such a tuple exists. The data structure is simpler than such a data structure for general directed graphs that can be obtained from results of Georgiadis and Tarjan. Disjoint can mean vertex- as well as edge-disjoint. As an application and main result we show that the data structure can be used to solve the 2-disjoint paths problem on directed acyclic graphs optimally, i.e., in linear time.
Publication Year: 2012
Publication Date: 2012-12-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 15
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot