A linear algorithms for the two paths problem on permutation graphs

DOI10.7151/DMGT.1013MaRDI QIDQ4882588zbMATH OpenOpenAlexFDO

Authors C. P. Gopalakrishnan, C. Pandu Rangan

Publication date 26 August 1996

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.7151/dmgt.1013

zbMATH Keywords

algorithmbridgeconnectivitydisjoint pathspermutation graphtwo paths problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 4117882
• Linear structure of bipartite permutation graphs and the longest path problem
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• STACS 2004
• Solving the 2-disjoint paths problem in nearly linear time
• scientific article; zbMATH DE number 140475
• An efficient algorithm to find next-to-shortest path on permutation graphs
• LINEAR-TIME ALGORITHMS FOR DISJOINT TWO-FACE PATHS PROBLEMS IN PLANAR GRAPHS
• Solving the shortest-paths problem on bipartite permutation graphs efficiently

Cited in

(7)

• Linear structure of bipartite permutation graphs and the longest path problem
• Polynomial time algorithm for constructing vertex-disjoint paths in transposition graphs
• scientific article; zbMATH DE number 1555936 (Why is no real title available?)
• scientific article; zbMATH DE number 4117882 (Why is no real title available?)
• Edge-disjoint paths in permutation graphs
• A linear time algorithm for finding all hinge vertices of a permutation graph
• A simple solution to the two paths problem in planar graphs

This page was built for publication: A linear algorithms for the two paths problem on permutation graphs

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