Parallel algorithms on interval graphs

DOI10.1051/ITA/1995290604511MaRDI QIDQ4359285zbMATH OpenOpenAlexFDO

Authors V. B. Balayogan, C. Pandu Rangan

Publication date 29 January 1998

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92518

zbMATH Keywords

breadth first search treesdepth first search

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 123468
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• scientific article; zbMATH DE number 3892606
• Some parallel algorithms on interval graphs
• Parallel computation on interval graphs: algorithms and experiments

Cites work

• A unified approach to domination problems on interval graphs
• Depth-first search is inherently sequential
• Efficient Parallel Algorithms for a Class of Graph Theoretic Problems
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 922870 (Why is no real title available?)
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Probabilistic parallel prefix computation
• Some parallel algorithms on interval graphs

Cited in

(14)

• Optimal parallel algorithms for finding cut vertices and bridges of interval graphs
• Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs
• Parallel algorithms for connectivity problems on interval graphs
• Designing efficient parallel algorithms on interval graphs
• Efficient neighborhood encoding for interval graphs and permutation graphs and O(n) breadth-first search
• scientific article; zbMATH DE number 123468 (Why is no real title available?)
• scientific article; zbMATH DE number 1955841 (Why is no real title available?)
• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• Parallel computation on interval graphs: algorithms and experiments
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• Efficient Parallel Algorithms for Chordal Graphs
• Interval Graph Problems on Reconfigurable Meshes
• Highly parallelizable problems on sorted intervals
• Recognizing and representing proper interval graphs in parallel using merging and sorting

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

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