Optimal computation of shortest paths on doubly convex bipartite graphs

DOI10.1016/S0898-1221(99)00201-1MaRDI QIDQ1963107zbMATH OpenFDO

Authors Lin Chen

Publication date 20 January 2000

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0898-1221(99)00201-1

zbMATH Keywords

all-pair shortest pathsdoubly convex bipartite graphsoptimal parallel algorithmsequential algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Programming involving graphs or networks (90C35)

Recommendations

• Efficient parallel algorithms for doubly convex-bipartite graphs
• An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs
• An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
• An all-pairs shortest path algorithm for bipartite graphs

Cites work

• A new upper bound on the complexity of the all pairs shortest path problem
• A note on two problems in connexion with graphs
• A Theorem on Boolean Matrices
• An Efficient Parallel Biconnectivity Algorithm
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• Bipartite permutation graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient parallel algorithms for bipartite permutation graphs
• Efficient parallel algorithms for doubly convex-bipartite graphs
• scientific article; zbMATH DE number 1088276 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Matrix multiplication via arithmetic progressions
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• ON THE POWER OF SOME PRAM MODELS
• Optimal parallel time bounds for the maximum clique problem on intervals
• Parallel recognition of the consecutive ones property with applications
• Solving the shortest-paths problem on bipartite permutation graphs efficiently
• The Parallel Evaluation of General Arithmetic Expressions
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(5)

• Dijkstra's algorithm and L-concave function maximization
• An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
• An all-pairs shortest path algorithm for bipartite graphs
• Levinson’s Problem on Affine-Periodic Solutions
• Solving the shortest-paths problem on bipartite permutation graphs efficiently

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Optimal computation of shortest paths on doubly convex bipartite graphs

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