An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs

DOI10.1016/S0020-0190(98)00121-5zbMath1339.68205MaRDI QIDQ293380

Qian-Ping Gu, Shietung Peng

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001215?np=y

zbMATH Keywords

interconnection networksdisjoint pathsoff-line routing algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

On the problem of determining which \((n, k)\)-star graphs are Cayley graphs ⋮ On strong Menger-connectivity of star graphs ⋮ Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph ⋮ Linearly many faults in Cayley graphs generated by transposition trees ⋮ Unnamed Item

Cites Work

• Node-to-set disjoint paths problem in star graphs
• Node-to-node cluster fault tolerant routing in star graphs
• On the existence of certain disjoint arcs in graphs
• A group-theoretic model for symmetric interconnection networks
• On the Computational Complexity of Combinatorial Problems
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs