Calculating a relational program for transitive reductions of strongly connected graphs

DOI10.1007/3-540-36280-0_18MaRDI QIDQ4415086zbMATH OpenFDO

Authors Rudolf Berghammer, Thorsten Hoffmann

Publication date 28 July 2003

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

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2561/25610258.htm

Mathematics Subject Classification ID

Cylindric and polyadic algebras; relation algebras (03G15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An algorithm for transitive reduction of an acyclic graph
• On the calculation of transitive reduction-closure of orders
• On building the transitive reduction of a two-dimensional poset
• Algorithms for transitive closure
• Finding a minimal transitive reduction in a strongly connected digraph within linear time

Cited in

(4)

• Two graph algorithms derived
• Relational characterisations of paths
• Parallel algorithms for transitive reduction for weighted graphs
• Simple rectangle-based functional programs for computing reflexive-transitive closures

Describes a project that uses

Uses Software

• RelView

This page was built for publication: Calculating a relational program for transitive reductions of strongly connected graphs

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