Problema de la amplitud

 A variant of the minimax path problem has also been considered for sets of points in the Euclidean plane. As in the undirected graph problem, this Euclidean minimax path problem can be solved efficiently by finding a Euclidean minimum spanning tree: every path in the tree is a minimax path. However, the problem becomes more complicated when a path is desired that not only minimizes the hop length but also, among paths with the same hop length, minimizes or approximately minimizes the total length of the path. The solution can be approximated using geometric spanners.[1]

In number theory, the unsolved Gaussian moat problem asks whether or not minimax paths in the Gaussian prime numbers have bounded or unbounded minimax length. That is, does there exist a constant B such that, for every pair of points p and q in the infinite Euclidean point set defined by the Gaussian primes, the minimax path in the Gaussian primes between p and q has minimax edge length at most B?[2]  

References

↑ Pollack, Maurice (1960), "The maximum capacity through a network", Operations Research 8 (5): 733–736, doi:10.1287/opre.8.5.733, JSTOR 167387 ↑ Shacham, N. (1992), "Multicast routing of hierarchical data", IEEE International Conference on Communications (ICC '92) 3, pp. 1217–1221, doi:10.1109/ICC.1992.268047 ; Wang, Zheng; Crowcroft, J. (1995), "Bandwidth-delay based routing algorithms", IEEE Global Telecommunications Conference (GLOBECOM '95) 3, pp. 2129–2133, doi:10.1109/GLOCOM.1995.502780 1 2 3 Schulze, Markus (2011), "A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method", Social Choice and Welfare 36 (2): 267–303, doi:10.1007/s00355-010-0475-4 1 2 Fernandez, Elena; Garfinkel, Robert; Arbiol, Roman (1998), "Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths", Operations Research 46 (3): 293–304, doi:10.1287/opre.46.3.293, JSTOR 222823 1 2 Ullah, E.; Lee, Kyongbum; Hassoun, S. (2009), "An algorithm for identifying dominant-edge metabolic pathways", IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009), pp. 144–150 1 2 Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "7.3 Capacity Scaling Algorithm", Network Flows: Theory, Algorithms and Applications, Prentice Hall, pp. 210–212, ISBN 0-13-617549-X 1 2 Berman, Oded; Handler, Gabriel Y. (1987), "Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations", Transportation Science 21 (2): 115–122, doi:10.1287/trsc.21.2.115 ↑ Hu, T. C. (1961), "The maximum capacity route problem", Operations Research 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055 1 2 Punnen, Abraham P. (1991), "A linear time algorithm for the maximum capacity path problem", European Journal of Operational Research 53 (3): 402–404, doi:10.1016/0377-2217(91)90073-5 ↑ Malpani, Navneet; Chen, Jianer (2002), "A note on practical construction of maximum bandwidth paths", Information Processing Letters 83 (3): 175–180, doi:10.1016/S0020-0190(01)00323-4, MR 1904226 ↑ Camerini, P. M. (1978), "The min-max spanning tree problem and some extensions", Information Processing Letters 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3 1 2 3 Kaibel, Volker; Peinhardt, Matthias A. F. (2006), On the bottleneck shortest path problem (PDF), ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin ↑ Leclerc, Bruno (1981), "Description combinatoire des ultramétriques", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (in French) (73): 5–37, 127, MR 623034 ↑ Demaine, Erik D.; Landau, Gad M.; Weimann, Oren (2009), "On Cartesian trees and range minimum queries", Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Lecture Notes in Computer Science 5555, pp. 341–353, doi:10.1007/978-3-642-02927-1_29 ↑ More specifically, the only kind of tie that the Schulze method fails to break is between two candidates who have equally wide paths to each other.↑ See Jesse Plamondon-Willard, Board election to use preference voting, May 2008; Mark Ryan, 2008 Wikimedia Board Election results, June 2008; 2008 Board Elections, June 2008; and 2009 Board Elections, August 2009.↑ Duan, Ran; Pettie, Seth (2009), "Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths", Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '09), pp. 384–391 . For an earlier algorithm that also used fast matrix multiplication to speed up all pairs widest paths, see Vassilevska, Virginia; Williams, Ryan; Yuster, Raphael (2007), "All-pairs bottleneck paths for general graphs in truly sub-cubic time", Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC '07), New York: ACM, pp. 585–589, doi:10.1145/1250790.1250876, MR 2402484  and Chapter 5 of Vassilevska, Virginia (2008), Efficient Algorithms for Path Problems in Weighted Graphs (PDF), Ph.D. thesis, Report CMU-CS-08-147, Carnegie Mellon University School of Computer Science 1 2 Gabow, Harold N.; Tarjan, Robert E. (1988), "Algorithms for two bottleneck optimization problems", Journal of Algorithms 9 (3): 411–417, doi:10.1016/0196-6774(88)90031-4, MR 955149 ↑ Han, Yijie; Thorup, M. (2002), "Integer sorting in O(n√log log n) expected time and linear space", Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), pp. 135–144, doi:10.1109/SFCS.2002.1181890 .↑ Bose, Prosenjit; Maheshwari, Anil; Narasimhan, Giri; Smid, Michiel; Zeh, Norbert (2004), "Approximating geometric bottleneck shortest paths", Computational Geometry. Theory and Applications 29 (3): 233–249, doi:10.1016/j.comgeo.2004.04.003, MR 2095376 ↑ Gethner, Ellen; Wagon, Stan; Wick, Brian (1998), "A stroll through the Gaussian primes", American Mathematical Monthly 105 (4): 327–337, doi:10.2307/2589708, MR 1614871 .