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

DOI10.1016/S0020-0190(00)00064-8zbMath1339.05396OpenAlexW1979140102MaRDI QIDQ294772

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

weighted graphdepth-first searchmin-transitivitysimilarity relation

Mathematics Subject Classification ID

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

Related Items (1)

Algorithms for computing the min-transitive closure and associated partition tree of a symmetric fuzzy relation.

Cites Work

• Unnamed Item
• Unnamed Item
• A fast algorithm for finding the compact sets
• An optimal algorithm for finding compact sets
• The min-max composition rule and its superiority over the usual max-min composition rule
• Similarity relations, fuzzy linear orders, and fuzzy partial orders
• On the computational power of pushdown automata

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