Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs

DOI10.1002/NET.20356MaRDI QIDQ3057177zbMATH OpenOpenAlexFDO

Authors Satoshi Fujita

Publication date 24 November 2010

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20356

zbMATH Keywords

matchingroutingtransposition graphvertex-disjoint paths

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Shortest two disjoint paths in polynomial time
• scientific article; zbMATH DE number 1555936
• A linear algorithms for the two paths problem on permutation graphs
• scientific article; zbMATH DE number 871922
• Shortest two disjoint paths in polynomial time

Cites work

• A group-theoretic model for symmetric interconnection networks
• Bisection width of transposition graphs
• Constructing vertex-disjoint paths in \((n, k)\)-star graphs
• scientific article; zbMATH DE number 50596 (Why is no real title available?)
• Node-to-set disjoint paths problem in star graphs
• Node‐disjoint paths and related problems on hierarchical cubic networks
• Transposition Graphs
• Transposition networks as a class of fault-tolerant robust networks
• Vertex disjoint paths on clique-width bounded graphs

Cited in

(4)

• Disjoint Hamilton cycles in transposition graphs
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks
• Subnetwork reliability analysis about complete-transposition graph networks

Describes a project that uses

Uses Software

• Mathematica

This page was built for publication: Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs

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