Finding a minimal transitive reduction in a strongly connected digraph within linear time

DOI10.1007/3-540-52292-1_18MaRDI QIDQ4694756zbMATH OpenFDO

Authors Klaus Simon

Publication date 29 June 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11850/68865

zbMATH Keywords

algorithmdepth-first searchdirected graphlinear timeminimal transitive reductionstrongly connected digraphtransitive closure

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) 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
• scientific article; zbMATH DE number 3958732
• Linear-time modular decomposition of directed graphs
• Minimal equivalent subgraphs containing a given set of arcs
• scientific article; zbMATH DE number 6783482

Cited in

(7)

• The minimum spanning strong subdigraph problem is fixed parameter tractable
• The diameter of the stable marriage polytope: bounding from below
• Calculating a relational program for transitive reductions of strongly connected graphs
• Polyhedral aspects of stable marriage
• Minimal equivalent subgraphs containing a given set of arcs
• Finding strong components using depth-first search
• On the calculation of transitive reduction-closure of orders

This page was built for publication: Finding a minimal transitive reduction in a strongly connected digraph within linear time

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