On the calculation of transitive reduction-closure of orders

DOI10.1016/0012-365X(93)90164-OMaRDI QIDQ686479zbMATH OpenFDO

Authors M. Morvan, M. A. Habib, Jean-Xavier Rampon

Publication date 13 March 1994

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

rank functiontop down algorithm

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algorithm for transitive reduction of an acyclic graph
• Complexité de problèmes liés aux graphes sans circuit
• scientific article; zbMATH DE number 3958732
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
• Transitive closure for restricted classes of partial orders

Cites work

• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3635493 (Why is no real title available?)
• scientific article; zbMATH DE number 219269 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• scientific article; zbMATH DE number 3340124 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A transitive closure algorithm
• An improved algorithm for transitive closure on acyclic digraphs
• Complexité de problèmes liés aux graphes sans circuit
• Incremental modular decomposition
• The Recognition of Series Parallel Digraphs
• The Transitive Reduction of a Directed Graph
• Transitive closure for restricted classes of partial orders

Cited in

(12)

• Interval graph representation with given interval and intersection lengths
• Computing the jump number on semi-orders is polynomial
• On building the transitive reduction of a two-dimensional poset
• Extending reduction orderings to ACU-compatible reduction orderings
• Mixed-integer linear programming for resource leveling problems
• scientific article; zbMATH DE number 1953900 (Why is no real title available?)
• Calculating exact transitive closure for a normalized affine integer tuple relation
• Algorithms for longest chains in pseudo-transitive graphs
• Complexité de problèmes liés aux graphes sans circuit
• scientific article; zbMATH DE number 1538060 (Why is no real title available?)
• Algorithms for transitive closure
• scientific article; zbMATH DE number 3958732 (Why is no real title available?)

This page was built for publication: On the calculation of transitive reduction-closure of orders

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