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

DOI10.1016/S0020-0190(00)00064-8zbMATH Open1339.05396OpenAlexW1979140102MaRDI QIDQ294772FDOQ294772

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the computational power of pushdown automata
• 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
• Title not available (Why is that?)

Cited In (2)

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

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)