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...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2000-06, Vol.74 (5), p.215-220
Main Author: Kundu, Sukhamay
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!
Description
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