Parallel interval order recognition and construction of interval representations

DOI10.1016/0304-3975(95)80011-5MaRDI QIDQ673637zbMATH OpenOpenAlexFDO

Authors Michael A. Bender, Michel Gastaldo, M. 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)

Recommendations

• Parallel \(N\)-free order recognition
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• New sequential and parallel algorithms for interval graph recognition
• An efficient parallel algorithm for scheduling interval ordered tasks
• scientific article; zbMATH DE number 1759465

Cites work

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

Cited in

(6)

• Algorithmic characterizations of interval orderd hypergraphs and applications
• Parallel \(N\)-free order recognition
• scientific article; zbMATH DE number 1533814 (Why is no real title available?)
• scientific article; zbMATH DE number 1554937 (Why is no real title available?)
• Counting endpoint sequences for interval orders and interval graphs
• New sequential and parallel algorithms for interval graph recognition

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

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