Search
Close this search box.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

A Faster Algorithm for Least Deviant Path

Ronald Dutton 1, William Klostermeyer2
1Department of Computer Science University of Central Florida Orlando, FL 32816
2Department Statistics and Computer Science West Virginia University Morgantown, WV 26506-6330
  • Published: 28/02/1999

Abstract

The least deviant path was defined by Klostermeyer \([1]\) as the path between two vertices \(u\) and \(v\) that minimizes the difference between the largest and smallest weights on the path. This paper presents an \(O(E \log E)\) time algorithm for this problem in undirected graphs, improving upon the previously given \(O(E^{1.793})\) time algorithm.
The same algorithm can also be used to solve the problem in \(O(VE)\) time in directed graphs.

Information
Guidelines
CP Initiatives
Follow CP
Facebook Twitter Linkedin
1970-2024 CP (Manitoba, Canada) unless otherwise stated.
Citation
Ronald Dutton , William Klostermeyer. A Faster Algorithm for Least Deviant Path[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 029. 33-40. DOI: .