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

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, Balancing problems in acyclic networks, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, A new approach to all-pairs shortest paths on real-weighted graphs, Reachability for airline networks: fast algorithm for shortest path problem with time windows, Multi-commodity demand fulfillment via simultaneous pickup and delivery for a fast fashion retailer, Monge matrices make maximization manageable, Computing and listing \(st\)-paths in public transportation networks, Approximating minimum-cost graph problems with spanning tree edges, Information-theoretic feature selection with discrete \(k\)-median clustering, Analysis of linear structured systems using a primal-dual algorithm, Complexity and approximation results on the shared transportation problem, Minimum spanning paths and Hausdorff distance in finite ultrametric spaces, Matroid optimization with generalized constraints, Costly circuits, submodular schedules and approximate Carathéodory theorems, A new approach for the multiobjective minimum spanning tree, Finding extreme supported solutions of biobjective network flow problems: an enhanced parametric programming approach, Minimizing a linear multiplicative-type function under network flow constraints, An algorithm for the quickest path problem, An efficient implementation of a static move descriptor-based local search heuristic, Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization, A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs, Computing the sequence of \(k\)-cardinality assignments, Discrete convexity in joint winner property, Optimal channel allocation for several types of cellular radio networks, Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times, A FastMap-based algorithm for block modeling, Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, The point-to-point connection problem - analysis and algorithms, Personalized PageRank clustering: a graph clustering algorithm based on random walks, Shortest paths with shortest detours. A biobjective routing problem, All-pairs-shortest-length on strongly chordal graphs, The energy-constrained quickest path problem, On weighting two criteria with a parameter in combinatorial optimization problems, An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs, Nonlinear multi-output regression on unknown input manifold, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, The weak-heap data structure: variants and applications, Improved shortest path algorithms for nearly acyclic graphs, The \(b\)-branching problem in digraphs, Finding the most vital node of a shortest path., Minimum-cost flows in unit-capacity networks, How fast can we reach a target vertex in stochastic temporal graphs?, A shortest cycle for each vertex of a graph, Faster algorithm for optimum Steiner trees, Faster shortest paths in dense distance graphs, with applications, Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm, Scheduling for electricity cost in a smart grid, A new algorithm for reoptimizing shortest paths when the arc costs change, Geometric path problems with violations, Revisiting priority queues for image analysis, The weighted farthest color Voronoi diagram on trees and graphs., Shipping problems with body clock constraints., Finding the first \(K\) shortest paths in a time-window network., A new scaling algorithm for the minimum cost network flow problem, A biobjective Dijkstra algorithm, Fast approximation of matroid packing and covering, Temporal network optimization subject to connectivity constraints, Efficient algorithms for updating betweenness centrality in fully dynamic graphs, Dealing with residual energy when transmitting data in energy-constrained capacitated networks, An algorithm for finding the \(k\) quickest paths in a network, Fast geometric approximation techniques and geometric embedding problems, Finding the \(K\) shortest paths in a schedule-based transit network, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance, A combinatorial dynamic network trajectory reservation algorithm for connected autonomous vehicles, Faster algorithm to find anti-risk path between two nodes of an undirected graph, Partially dynamic maintenance of minimum weight hyperpaths, A spectral approach to the shortest path problem, Closest paths in graph drawings under an elastic metric, Min-max controllable risk problems, A faster approximation algorithm for the Steiner tree problem in graphs, The minimum spanning tree problem on a planar graph, On the inverse problem of linear programming and its application to minimum weight perfect \(k\)-matching, On the quickest path problem, Greedy differencing edge-contraction heuristic for the max-cut problem, An efficient algorithm for minimum-weight bibranching, Shortest path algorithms for nearly acyclic directed graphs, Class Steiner trees and VLSI-design, The partial sum criterion for Steiner trees in graphs and shortest paths, Reconstructing a history of recombinations from a set of sequences, The non-approximability of bicriteria network design problems, Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration, Minimization algorithms for sequential transducers, Some personal views on the current state and the future of locational analysis, Some new algorithms for location problems on networks, An algorithm for fractional assignment problems, Approximation algorithms for solving the line-capacitated minimum Steiner tree problem, Semi-dynamic breadth-first search in digraphs, A note on practical construction of maximum bandwidth paths., Efficient algorithms for finding the most vital edge of a minimum spanning tree, An external memory data structure for shortest path queries, Theory of 2-3 heaps, The expected complexity of Prim's minimum spanning tree algorithm, Algorithms for the constrained quickest path problem and the enumeration of quickest paths, Parallel algorithms for the assignment and minimum-cost flow problems, Finding the \(k\) quickest simple paths in a network, On an ordering problem in weighted hypergraphs, Minimization of travel time and weighted number of stops in a traffic-light network, Center problems with pos/neg weights on trees, An improved approximation algorithm for the uniform cost-distance Steiner tree problem, Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network, Augmenting weighted graphs to establish directed point-to-point connectivity, The all-pairs quickest path problem, A heuristic improvement of the Bellman-Ford algorithm, Finding the k shortest paths in parallel, Hollow Heaps, A survey of the all-pairs shortest paths problem and its variants in graphs, Improved algorithms for some competitive location centroid problems on paths, trees and graphs, An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces, Efficient parallel algorithms for shortest paths in planar graphs, DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS, Fast meldable priority queues, On the computation of fast data transmissions in networks with capacities and delays, Worst-Case Optimal Priority Queues via Extended Regular Counters, A note of an \(O(n^{3}/\log n)\) time algorithm for all pairs shortest paths, Length-constrained cycle partition with an application to UAV routing*, The K-D heap: An efficient multi-dimensional priority queue, A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs, Minimum weight euclidean matching and weighted relative neighborhood graphs, Searching among intervals and compact routing tables, Computing all efficient solutions of the biobjective minimum spanning tree problem, Faster All-Pairs Shortest Paths via Circuit Complexity, Total Variation on a Tree, Structured Connectivity Augmentation, Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids, Improved algorithm for all pairs shortest paths, Computing Weighted Strength and Applications to Partitioning, Tight lower and upper bounds for the complexity of canonical colour refinement, Solving all-pairs shortest path by single-source computations: theory and practice, Weighted approximate parameterized string matching, A faster strongly polynomial time algorithm to solve the minimum cost tension problem, Fibonacci helps to evacuate from a convex region in a grid network, Structured Connectivity Augmentation, An improved multiobjective shortest path algorithm, Generalised 2-circulant inequalities for the max-cut problem, A fully polynomial time approximation scheme for the probability maximizing shortest path problem, On envy-free perfect matching, A note on the 2-circulant inequalities for the MAX-cut problem, ANTS on a Plane, Controlled transitions between cupolets of chaotic systems, A Weighted K t,t -Free t-Factor Algorithm for Bipartite Graphs, Finding optimal non-datapath caching strategies via network flow, An \(O(n(m+n\log n)\log n)\) time algorithm to solve the minimum cost tension problem, Approximating the restricted 1-center in graphs, Algebraic theory on shortest paths for all flows, A short note on Layman permutations, Parameterized multi-scenario single-machine scheduling problems, Unnamed Item, Unnamed Item, A Filtering Technique for All Pairs Approximate Parameterized String Matching, Bayesian generalized network design, Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines, Unnamed Item, Enumerating Grid Layouts of Graphs, On the fast delivery problem with one or two packages, Efficient modelling of solute transport in heterogeneous media with discrete event simulation, Efficient privacy-preserving data merging and skyline computation over multi-source encrypted data, Finding a smallest odd hole in a claw-free graph using global structure, Smooth Heaps and a Dual View of Self-Adjusting Data Structures, Facets from gadgets, Faster Swap Edge Computation in Minimum Diameter Spanning Trees, On some new arithmetic properties of the generalized Lucas sequences, Cost-based filtering for shorter path constraints, Least solutions of equations over N, Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm, Density Independent Algorithms for Sparsifying k-Step Random Walks, Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs, Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs., The single train shortest route problem in a railyard, A tight analysis of the Katriel-Bodlaender algorithm for online topological ordering, An algorithm for checking whether the toric ideal of an affine monomial curve is a complete intersection, Shortest path queries in digraphs of small treewidth, Finding real-valued single-source shortest paths in o(n 3) expected time, The partial inverse minimum spanning tree problem when weight increase is forbidden, Algorithms for topology-free and alignment network queries, The first \(K\) shortest unique-arc walks in a traffic-light network, Improved algorithms for replacement paths problems in restricted graphs, Unnamed Item, Fully dynamic all pairs shortest paths with real edge weights, Unnamed Item, Finding \(K\) shortest looping paths with waiting time in a time--window network, On a Technique for Finding Running Tracks of Specific Length in a Road Network, Combinatorial auctions with decreasing marginal utilities, Bi-criteria path problem with minimum length and maximum survival probability, Priority queues on parallel machines, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, Optimal assignments with supervisions, How fast can we reach a target vertex in stochastic temporal graphs, A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression., Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems, Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models, Finding the k Shortest Paths, Rectilinear paths among rectilinear obstacles, Stabilizing Boolean networks by optimal event-triggered feedback control, Max-Balanced Hungarian Scalings, From Circuit Complexity to Faster All-Pairs Shortest Paths, A new separation algorithm for the Boolean quadric and cut polytopes, Optimal shortest path set problem in undirected graphs, Fast data transmission and maximal dynamic flow., A Faster Implementation of Zelikovsky's 11/6-Approximation Algorithm for the Steiner Problem in Graphs, Two-Levels-Greedy: a generalization of Dijkstra's shortest path algorithm, Ridesharing for emergency evacuation, Navigating Weighted Regions with Scattered Skinny Tetrahedra, Unnamed Item, A weight-scaling algorithm for \(f\)-factors of multigraphs, Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter, On matchings, T‐joins, and arc routing in road networks, Shortest paths in random weighted graphs, A novel pseudo‐polynomial approach for shortest path problems, Heuristics for the connected assignment problem in arrays, The dynamics of rank-maximal and popular matchings, Online learning of network bottlenecks via minimax paths, On the all-pairs shortest path algorithm of Moffat and Takaoka, A Bayesian spatial scan statistic for multinomial data, Solving third-order linear recurrence relations with applications to number theory and combinatorics, Efficient enumeration of the optimal solutions to the correlation clustering problem, Jacobi's bound: Jacobi's results translated in Kőnig's, Egerváry's and Ritt's mathematical languages, Improving a constructive heuristic for the general routing problem, Steiner problems on directed acyclic graphs, Priority-based bin packing with subset constraints, Shortest distances as enumeration problem, Weight biased leftist trees and modified skip lists, Path planning in a weighted planar subdivision under the Manhattan metric, Efficient algorithms for finding diversified top-\(k\) structural hole spanners in social networks, An efficient parallel algorithm for shortest paths in planar layered digraphs, Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs, Solving Jigsaw Puzzles by the Graph Connection Laplacian, Collaborative delivery on a fixed path with homogeneous energy-constrained agents, On the spanning trees of weighted graphs, The \(k\)-centrum multi-facility location problem, Faster shortest-path algorithms for planar graphs, An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model, Minimum-weight spanning tree algorithms. A survey and empirical study, Integer priority queues with decrease key in constant time and the single source shortest paths problem, On the shortest path problem with negative cost cycles, Some graph optimization problems with weights satisfying linear constraints, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, Cascade heap: towards time-optimal extractions, Unnamed Item, Faster algorithms for shortest path and network flow based on graph decomposition, Multilevel Artificial Neural Network Training for Spatially Correlated Learning, SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates, Regarding Goal Bounding and Jump Point Search, A Forward-Backward Single-Source Shortest Paths Algorithm, Unnamed Item, A Fast Approximate Skeleton with Guarantees for Any Cloud of Points in a Euclidean Space, Parametric Shortest-Path Algorithms via Tropical Geometry