Two Arc-Disjoint Paths in Eulerian Digraphs

DOI10.1137/S0895480196304970MaRDI QIDQ4210224zbMATH OpenOpenAlexFDO

Authors András Frank, Toshihide Ibaraki, Hiroshi Nagamochi

Publication date 21 September 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480196304970

zbMATH Keywords

disjoint pathsEulerian graphpolynomial time algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph theory (including graph drawing) in computer science (68R10)

Review text

A polynomial time algorithm is given for the following decision problem: Instance: An Eulerian digraph \(D\) and two pairs \(\{x_1,x_2\},\{y_1,y_2\}\) of its vertices. Question: Is there a choice of \(h,i,j,k\) with \(\{h,i\}=\{j,k\}=\{1,2\}\) such that there are arc-disjoint \(x_hy_j\) and \(x_iy_k\) paths?

Recommendations

• Two arc disjoint paths in Eulerian digraphs
• Weak Three-Linking in Eulerian Dgraphs
• (Arc-)disjoint flows in networks
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• On the complexity of the disjoint paths problem

Cited in

(7)

• (Arc-)disjoint flows in networks
• Arc-disjoint paths in decomposable digraphs
• scientific article; zbMATH DE number 6379051 (Why is no real title available?)
• Euler digraphs
• A linear time algorithm for finding three edge-disjoint paths in Eulerian networks
• Weak Three-Linking in Eulerian Dgraphs
• Two arc disjoint paths in Eulerian digraphs

This page was built for publication: Two Arc-Disjoint Paths in Eulerian Digraphs

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