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

DOI10.1016/S0020-0190(98)00121-5MaRDI QIDQ293380zbMATHFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 714464
• scientific article; zbMATH DE number 1439419
• Node-to-set disjoint paths problem in star graphs
• One-to-many node-disjoint paths in \((n,k)\)-star graphs
• An efficient algorithm for the \(k\)-pairwise disjoint paths problem in hypercubes

Cites work

• scientific article; zbMATH DE number 54299 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A group-theoretic model for symmetric interconnection networks
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Node-to-node cluster fault tolerant routing in star graphs
• Node-to-set disjoint paths problem in star graphs
• On the Computational Complexity of Combinatorial Problems
• On the existence of certain disjoint arcs in graphs

Cited in

(12)

• On disjoint shortest paths routing in interconnection networks: a case study in the star graph
• On strong Menger-connectivity of star graphs
• Node-to-set disjoint paths problem in star graphs
• Set-to-set disjoint paths in a folded hypercube
• On the problem of determining which \((n, k)\)-star graphs are Cayley 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
• Constructing vertex-disjoint paths in \((n, k)\)-star graphs
• Linearly many faults in Cayley graphs generated by transposition trees
• The Nova Graph: more disjoint paths with minimal graph augmentation
• scientific article; zbMATH DE number 714464 (Why is no real title available?)
• One-to-many node-disjoint paths in \((n,k)\)-star graphs
• scientific article; zbMATH DE number 2230273 (Why is no real title available?)

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

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