Optimal parallel algorithms on circular-arc graphs

DOI10.1016/0020-0190(89)90195-6zbMath0688.68046OpenAlexW28739840MaRDI QIDQ1263980

A. Srinivasa Rao, C. Pandu Rangan

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90195-6

zbMATH Keywords

parallel algorithmsEREW PRAMcircular-arc graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (6)

\(k\) best cuts for circular-arc graphs ⋮ Distributed algorithms for maximum cliques ⋮ Induced matchings in intersection graphs. ⋮ Parallel algorithms on circular-arc graphs ⋮ A survey of selected recent results on total domination in graphs ⋮ Independent packings in structured graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding maximum cliques on circular-arc graphs
• An efficient parallel algorithm for planarity
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• An Efficient Parallel Biconnectivity Algorithm
• Approximate Parallel Scheduling. Part I: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Parallel Merge Sort
• Stability in circular arc graphs
• Parallel Prefix Computation
• An Efficient Test for Circular-Arc Graphs

This page was built for publication: Optimal parallel algorithms on circular-arc graphs