Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph

DOI10.1080/00207169508804449MaRDI QIDQ4870967zbMATH OpenOpenAlexFDO

Authors Madhumangal Pal, G. P. Bhattacharjee

Publication date 8 April 1996

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207169508804449

zbMATH Keywords

parallel algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 123468
• Some parallel algorithms on interval graphs
• scientific article; zbMATH DE number 3892606
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Optimal parallel algorithm for shortest-paths problem on interval graphs
• scientific article; zbMATH DE number 1670650
• Efficient algorithms for centers and medians in interval and circular-arc graphs
• The optimal sequential and parallel algorithms to compute all hinge vertices on interval graphs
• An improved algorithm for the p-center problem on interval graphs with unit lengths
• Parallel algorithms on interval graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• A simple linear-time algorithm for computing the center of an interval graph
• A unified approach to domination problems on interval graphs
• A unified approach to parallel depth-first traversals of general trees
• An optimal algorithm to solve the all-pair shortest path problem on interval graphs
• Breadth-first traversal of trees and integer sorting in parallel
• Computation of the center and diameter of outerplanar graphs
• Parallel Merge Sort

Cited in

(12)

• An optimal algorithm to find centres and diameter of a circular-arc graph
• The \(k\)-neighbourhood-covering problem on interval graphs
• An improved algorithm for the p-center problem on interval graphs with unit lengths
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
• A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
• L(2,1)-labeling of interval graphs
• An Optimal Algorithm to Solve 2-Neighbourhood Covering Problem on Interval Graphs
• \(L(3, 2, 1)\)- and \(L(4, 3, 2, 1)\)-labeling problems on interval graphs
• A simple linear-time algorithm for computing the center of an interval graph
• Computation of diameter, radius and center of permutation graphs
• Minimum 2-tuple dominating set of an interval graph

This page was built for publication: Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph

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