A linear time algorithm for finding three edge-disjoint paths in Eulerian networks

DOI10.1007/978-3-642-11266-9_14MaRDI QIDQ3401090zbMATH OpenOpenAlexFDO

Authors Ignat Kolesnichenko, Ilya Razenshteyn, Maxim Babenko

Publication date 28 January 2010

Published in SOFSEM 2010: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1003.3085

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: Consider an undirected graph $G=(VG,EG)$ and a set of six emph{terminals} $T=set{s}_1,s_2,s_3,t_1,t_2,t_{3}subseteqVG$. The goal is to find a collection $calP$ of three edge-disjoint paths $P_1$, $P_2$, and $P_3$, where $P_i$ connects nodes $s_i$ and $t_i$ ($i=1,2,3$). Results obtained by Robertson and Seymour by graph minor techniques imply a polynomial time solvability of this problem. The time bound of their algorithm is $O(m^3)$ (hereinafter we assume $n:=absVG$, $m:=absEG$, $n=O(m)$). In this paper we consider a special, emph{Eulerian} case of $G$ and $T$. Namely, construct the emph{demand graph} $H=(VG,set{s}_1{t}_1,s_2{t}_2,s_3{t}_3)$. The edges of $H$ correspond to the desired paths in $calP$. In the Eulerian case the degrees of all nodes in the (multi-) graph $G+H$ ($=(VG,EGcupEH)$) are even. Schrijver showed that, under the assumption of Eulerianess, cut conditions provide a criterion for the existence of $calP$. This, in particular, implies that checking for existence of $calP$ can be done in $O(m)$ time. Our result is a combinatorial $O(m)$-time algorithm that constructs $calP$ (if the latter exists).

Recommendations

• The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• On the complexity of the disjoint paths problem
• Two Arc-Disjoint Paths in Eulerian Digraphs

Cited in

(3)

• Length 3 edge-disjoint paths is NP-hard
• Weak Three-Linking in Eulerian Dgraphs
• Two arc disjoint paths in Eulerian digraphs

This page was built for publication: A linear time algorithm for finding three edge-disjoint paths in Eulerian networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3401090)