Parallel interval order recognition and construction of interval representations

DOI10.1016/0304-3975(95)80011-5zbMath0873.68081OpenAlexW2039644187MaRDI QIDQ673637

Michel Gastaldo, Michael A. Bender, Michel Morvan

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0304-3975(95)80011-5

zbMATH Keywords

parallel random access machines

Mathematics Subject Classification ID

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

Related Items (1)

Parallel \(N\)-free order recognition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time and space algorithm to recognize interval orders
• Interval graphs and related topics
• Interval graphs and interval orders
• N-free posets as generalizations of series-parallel posets
• Sorting in constant number of row and column phases on a mesh
• A linear-time recognition algorithm for interval dags
• A labeling algorithm to recognize a line digraph and output its root graph
• Deterministic sorting in nearly logarithmic time on the hypercube and related computers
• On Comparability and Permutation Graphs
• Parallel Merge Sort
• Scheduling Interval-Ordered Tasks
• The Recognition of Series Parallel Digraphs
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Intransitive Indifference in Preference Theory: A Survey
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: Parallel interval order recognition and construction of interval representations