Planar stage graphs: Characterizations and applications

DOI10.1016/S0304-3975(96)00201-0MaRDI QIDQ1392202zbMATH OpenOpenAlexFDO

Authors Frank Bauernöppel, Evangelos Kranakis, D. Krizanc, Anil Maheshwari, Jörg-Rüdiger Sack

Publication date 23 July 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(96)00201-0, https://ir.library.carleton.ca/pub/1363

zbMATH Keywords

planar stage graphs

Mathematics Subject Classification ID

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

Recommendations

• Stage-graph representations
• On two-processor scheduling and maximum matching in permutation graphs
• OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION GRAPHS
• Finding a maximum matching in a permutation graph

Cites work

• A linear-time algorithm for a special case of disjoint set union
• A simple optimal parallel algorithm for reporting paths in a tree
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Intersecting Line Segments in Parallel with an Output-Sensitive Number of Processors
• On Comparability and Permutation Graphs
• Optimal scheduling for two-processor systems
• Optimal Sequencing of Two Equivalent Processors
• Parallel Merge Sort
• Scheduling Graphs on Two Processors
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(4)

• Stage-graph representations
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• On the Characterization of Plane Bus Graphs
• Ray shooting from convex ranges

This page was built for publication: Planar stage graphs: Characterizations and applications

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