Transitive closure for restricted classes of partial orders

DOI10.1007/BF00383402MaRDI QIDQ1182064zbMATH OpenFDO

Authors Tze-Heng Ma, Jeremy P. Spinrad

Publication date 27 June 1992

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00383402

zbMATH Keywords

\(N\)-free partial ordersefficient algorithmspermutation graphtransitive closuretransitive reductiontwo-dimensional partial orders

Mathematics Subject Classification ID

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

Recommendations

• On the calculation of transitive reduction-closure of orders
• On building the transitive reduction of a two-dimensional poset
• Cycle-free partial orders and chordal comparability graphs

Cites work

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

Cited in

(9)

• Transitive closure and related semiring properties via eliminants
• Parallel \(N\)-free order recognition
• On the existence and construction of T-transitive closures.
• Remark on ``Toom's partial order is transitive
• On building the transitive reduction of a two-dimensional poset
• scientific article; zbMATH DE number 1153387 (Why is no real title available?)
• A first-order version of Pfaffian closure
• Confluent Hasse Diagrams
• On the calculation of transitive reduction-closure of orders

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

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