Loading…
An optimal [formula omitted] algorithm for computing the min-transitive closure of a weighted graph
We obtain an optimal O(N 2) algorithm for computing the min-transitive closure of a weighted undirected (symmetric) graph G on N nodes, which improves the previous bound of O(N 3) . The algorithm is based on the observation that a connected graph G has a spanning tree T such that the min-transitive...
Saved in:
Published in: | Information processing letters 2000-06, Vol.74 (5), p.215-220 |
---|---|
Main Author: | |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | We obtain an optimal
O(N
2)
algorithm for computing the min-transitive closure of a weighted undirected (symmetric) graph
G on
N nodes, which improves the previous bound of
O(N
3)
. The algorithm is based on the observation that a connected graph
G has a spanning tree
T such that the min-transitive closure of
G is the same as that of
T . |
---|---|
ISSN: | 0020-0190 1872-6119 |
DOI: | 10.1016/S0020-0190(00)00064-8 |