Fibonacci heaps and their uses in improved network optimization algorithms

DOI10.1145/28869.28874zbMath1412.68048OpenAlexW2084224084WikidataQ55866065 ScholiaQ55866065MaRDI QIDQ5225293

Michael L. Fredman, Robert Endre Tarjan

Publication date: 19 July 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/28869.28874

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items (only showing first 100 items - show all)

Finding reliable shortest paths in road networks under uncertainty ⋮ General cops and robbers games with randomness ⋮ Fair matchings and related problems ⋮ The minmax regret robust shortest path problem in a finite multi-scenario model ⋮ On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ Algorithmic analysis of priority-based bin packing ⋮ The pairing heap: A new form of self-adjusting heap ⋮ Shortest paths in Euclidean graphs ⋮ Finding the detour-critical edge of a shortest path between two nodes ⋮ Fast and fine quickest path algorithm ⋮ Multi-neighborhood based iterated tabu search for routing and wavelength assignment problem ⋮ Optimal piecewise linear motion of an object among obstacles ⋮ Scheduling jobs with fixed start and end times ⋮ A simple algorithm for replacement paths problem ⋮ A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem ⋮ A Dijkstra-type algorithm for dynamic games ⋮ A sequential dual simplex algorithm for the linear assignment problem ⋮ Bi-criteria sequencing of courses and formation of classes for a bottleneck classroom ⋮ A polynomial algorithm for the multicriteria cent-dian location problem ⋮ A computational study of efficient shortest path algorithms ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic ⋮ Shortest enclosing walks and cycles in embedded graphs ⋮ Solving shortest paths efficiently on nearly acyclic directed graphs ⋮ An improved Dijkstra's shortest path algorithm for sparse network ⋮ Optimal paths in weighted timed automata ⋮ The k most vital arcs in the shortest path problem ⋮ Two fast algorithms for all-pairs shortest paths ⋮ Algorithms for shortest paths and \(d\)-cycle problems ⋮ Spatially-decaying aggregation over a network ⋮ Approximate distance oracles for graphs with dense clusters ⋮ Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs ⋮ Simulation relations for pattern matching in directed graphs ⋮ Sharing information for the all pairs shortest path problem ⋮ Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs ⋮ Algorithms to test open set condition for self-similar set related to P.V. numbers ⋮ A faster computation of all the best swap edges of a shortest paths tree ⋮ A one-shot deviation principle for stability in matching problems ⋮ A method to evaluate routing policy through \(p\) minimal paths for stochastic case ⋮ System reliability for quickest path problems under time threshold and budget ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh ⋮ Finding the shortest paths by node combination ⋮ Algorithms for searching paths in huge graphs ⋮ An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem ⋮ The quickest path problem ⋮ An algorithm for load balancing in multiprocessor systems ⋮ Retiming synchronous circuitry ⋮ The saga of minimum spanning trees ⋮ Parameterized matching with mismatches ⋮ An efficient solution algorithm for solving multi-class reliability-based traffic assignment problem ⋮ A survey of geodesic paths on 3D surfaces ⋮ Stochastic flow networks via multiple paths under time threshold and budget constraint ⋮ A pointer-free data structure for merging heaps and min-max heaps ⋮ A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time ⋮ Algorithms for the quickest path problem and the enumeration of quickest paths ⋮ Shortest path algorithms: A computational study with the C programming language ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ Augmenting graphs to minimize the diameter ⋮ Faster separation of 1-wheel inequalities by graph products ⋮ Two new criteria for finding Steiner hulls in Steiner tree problems ⋮ Processing time-dependent shortest path queries without pre-computed speed information on road networks ⋮ Solving the shortest-paths problem on bipartite permutation graphs efficiently ⋮ On the point-to-point connection problem ⋮ Connected domination and Steiner set on weighted permutation graphs ⋮ The point-to-point delivery and connection problems: Complexity and algorithms ⋮ Shortest path computations in source-deplanarized graphs ⋮ Monge and feasibility sequences in general flow problems ⋮ An exterior simplex type algorithm for the minimum cost network flow problem ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ Incremental single-source shortest paths in digraphs with arbitrary positive arc weights ⋮ Two skew-binary numeral systems and one application ⋮ Spare routing problem with \(p\) minimal paths for time-based stochastic flow networks ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ On transmission time through \(k\) minimal paths of a capacitated-flow network ⋮ A faster algorithm for the single source shortest path problem with few distinct positive lengths ⋮ Approximation algorithms for shortest descending paths in terrains ⋮ Improved algorithms for the \(k\) simple shortest paths and the replacement paths problems ⋮ Fast algorithms for placing large entries along the diagonal of a sparse matrix ⋮ Parameterized searching with mismatches for run-length encoded strings ⋮ Single source shortest paths in \(H\)-minor free graphs ⋮ Partial-matching RMS distance under translation: combinatorics and algorithms ⋮ The simultaneous strong metric dimension of graph families ⋮ On a pair of job-machine assignment problems with two stages ⋮ The shortest path problem with forbidden paths ⋮ Reflected min-Max heaps ⋮ Exploiting sparsity in pricing routines for the capacitated arc routing problem ⋮ The number of tests required to search an unordered table ⋮ Approximate labelled subtree homeomorphism ⋮ Time version of the shortest path problem in a stochastic-flow network ⋮ Finding non-dominated bicriteria shortest pairs of disjoint simple paths ⋮ Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation ⋮ Finding optimal paths in MREP routing ⋮ An open vehicle routing problem metaheuristic for examining wide solution neighborhoods ⋮ A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing ⋮ A linear time algorithm for the maximum capacity path problem ⋮ A fast algorithm for minimum weight odd circuits and cuts in planar graphs ⋮ Integrated distribution and loading planning via a compact metaheuristic algorithm ⋮ Efficient computation of Lyapunov functions for Morse decompositions ⋮ Fast algorithms for the undirected negative cost cycle detection problem

This page was built for publication: Fibonacci heaps and their uses in improved network optimization algorithms