Transitive closure for restricted classes of partial orders

DOI10.1007/BF00383402zbMath0737.06001MaRDI QIDQ1182064

Tze-Heng Ma, Jeremy P. Spinrad

Publication date: 27 June 1992

Published in: Order (Search for Journal in Brave)

zbMATH Keywords

transitive closureefficient algorithmspermutation graphtransitive reductiontwo-dimensional partial orders\(N\)-free partial orders

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

On building the transitive reduction of a two-dimensional poset ⋮ Parallel \(N\)-free order recognition ⋮ On the calculation of transitive reduction-closure of orders ⋮ Confluent Hasse Diagrams

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting endpoint sequences for interval orders and interval graphs
• Matrix multiplication via arithmetic progressions
• On some complexity properties of N-free posets and posets with bounded decomposition diameter
• A labeling algorithm to recognize a line digraph and output its root graph
• Cycle-free partial orders and chordal comparability graphs
• \(P_ 4\)-trees and substitution decomposition
• Single Machine Scheduling with Precedence Constraints of Dimension 2
• The Complexity of the Partial Order Dimension Problem
• On Comparability and Permutation Graphs
• Searching in 2-dimensional partial orders
• Incremental modular decomposition
• Scheduling Interval-Ordered Tasks
• The Recognition of Series Parallel Digraphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Partial orders of dimension 2
• Partially Ordered Sets

This page was built for publication: Transitive closure for restricted classes of partial orders