Parallel algorithms for connectivity problems on interval graphs

DOI10.1016/0020-0190(95)00128-YMaRDI QIDQ1350233zbMATH OpenOpenAlexFDO

Authors Sanjeev Saxena, N. Malahal Rao

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00128-y

zbMATH Keywords

Parallel algorithmsInterval graphBiconnected componentsConnected components

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Parallel algorithms on interval graphs
• Highly parallelizable problems on sorted intervals
• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• Parallel computation on interval graphs: algorithms and experiments

Cites work

• scientific article; zbMATH DE number 1003255 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• Optimal computation of prefix sums on a binary tree of processors
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Parallel concepts in graph theory
• Randomized range-maxima in nearly-constant parallel time
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Some parallel algorithms on interval graphs
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs

Cited in

(10)

• New sequential and parallel algorithms for interval graph recognition
• Parallel algorithms for connectivity problems in graph theory
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Approximating unweighted connectivity problems in parallel
• scientific article; zbMATH DE number 3930349 (Why is no real title available?)
• Designing efficient parallel algorithms on interval graphs
• Parallel Complexity of the Connected Subgraph Problem
• Parallel algorithms for maximum matching in complements of interval graphs and related problems
• Fast algorithms for identifying maximal common connected sets of interval graphs
• scientific article; zbMATH DE number 4037198 (Why is no real title available?)

This page was built for publication: Parallel algorithms for connectivity problems on interval graphs

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