An optimal O(N^2) algorithm for computing the min-transitive closure of a weighted graph

DOI10.1016/S0020-0190(00)00064-8MaRDI QIDQ294772zbMATH OpenOpenAlexFDO

Authors Sukhamay Kundu

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019000000648?np=y

zbMATH Keywords

depth-first searchweighted graphmin-transitivitysimilarity relation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithms for computing the min-transitive closure and associated partition tree of a symmetric fuzzy relation.
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
• An optimal algorithm for computing the max-min transitive closure of a fuzzy similarity matrix
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 41471 (Why is no real title available?)
• scientific article; zbMATH DE number 3800811 (Why is no real title available?)
• A fast algorithm for finding the compact sets
• An optimal algorithm for finding compact sets
• On the computational power of pushdown automata
• Similarity relations, fuzzy linear orders, and fuzzy partial orders
• The min-max composition rule and its superiority over the usual max-min composition rule

Cited in

(2)

• An optimal algorithm for finding compact sets
• Algorithms for computing the min-transitive closure and associated partition tree of a symmetric fuzzy relation.

This page was built for publication: An optimal \(O(N^{2})\) algorithm for computing the min-transitive closure of a weighted graph

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