# Transitive Reduction Problem of Directed Graphs (Transitive Reduction Problem)

Jump to navigation
Jump to search

## Description

A directed graph $G^t$ is said to be a transitive reduction of the directed graph $G$ provided that (i) $G$ has a directed path from vertex $u$ to vertex $v$ if and only if $G$ has a directed path from vertex $u$ to vertex $v$, and (ii) there is no graph with fewer arcs than $G^t$ satisfying condition (i). The problem asks to find such a graph $G^t$ for a given digraph $G$.

## Parameters

$n$: number of vertices

$m$: number of edges

## Table of Algorithms

Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|

Aho, Garey & Ullman | 1972 | $O(n^omega)$ where omega is the exponent on boolean matrix multiplication | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1972 | $O(n^{2.807})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1978 | $O(n^{2.8})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1979 | $O(n^{2.78})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1980 | $O(n^{2.52})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1980 | $O(n^{2.518})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1981 | $O(n^{2.495})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1986 | $O(n^{2.48})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 1990 | $O(n^{2.372})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 2014 | $O(n^{2.373})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Aho, Garey & Ullman | 2014 | $O(n^{2.371})$ | $O(n^{2})$ | Exact | Deterministic | Time |

Gries, Martin | 1989 | $O(n^{3})$ | $O(n^{2})$ | Exact | Deterministic | Time |