Trans-dichotomous algorithms for minimum spanning trees and shortest paths
From MaRDI portal
Publication:1329156
DOI10.1016/S0022-0000(05)80064-9zbMath0806.68057OpenAlexW2164485560WikidataQ55951522 ScholiaQ55951522MaRDI QIDQ1329156
Michael L. Fredman, Dan E. Willard
Publication date: 29 June 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80064-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Iterated nearest neighbors and finding minimal polytopes, A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges, Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search, Universal Reconstruction of a String, Space-efficient indexes for forbidden extension queries, Using sparsification for parametric minimum spanning tree problems, Proof labeling schemes, All-pairs shortest paths and the essential subgraph, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, Smoothing the Gap Between NP and ER, Input-output networks offer new insights of economic structure, Shortest paths algorithms: Theory and experimental evaluation, Full-fledged real-time indexing for constant size alphabets, Efficient range searching for categorical and plain data, Validating the Knuth-Morris-Pratt failure function, fast and online, On compressing permutations and adaptive sorting, Trans-dichotomous algorithms without multiplication — some upper and lower bounds, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Cross-document pattern matching, Random access in persistent strings and segment selection, Distributed verification of minimum spanning trees, Unnamed Item, The saga of minimum spanning trees, Path Minima in Incremental Unrooted Trees, Augmenting graphs to minimize the diameter, Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem, Dynamic Planar Range Maxima Queries, FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING, Color-spanning localized query, Well-separated pair decomposition in linear time?, Improved algorithms for replacement paths problems in restricted graphs, A faster algorithm for the single source shortest path problem with few distinct positive lengths, Faster shortest-path algorithms for planar graphs, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Unnamed Item, Universal reconstruction of a string, A fast algorithm for data collection along a fixed track, From Regular Expression Matching to Parsing, Linear-time algorithms for parametric minimum spanning tree problems on planar graphs, Fusion trees can be implemented with \(AC^0\) instructions only, Finding the k Shortest Paths, Rectilinear paths among rectilinear obstacles, Faster compressed quadtrees, Partitioned event graph: formalizing LP-based modelling of parallel discrete-event simulation, Data structures for categorical path counting queries, From regular expression matching to parsing, Random Access to Grammar-Compressed Strings and Trees, Lower bounds for dynamic algebraic problems, \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm, On constructing the elimination tree, Linear-space data structures for range frequency queries on arrays and trees
Cites Work
- Unnamed Item
- Linear verification for spanning trees
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Surpassing the information theoretic bound with fusion trees
- Faster algorithms for the shortest path problem
- Hash functions for priority queues
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
- Design and implementation of an efficient priority queue
- Fibonacci heaps and their uses in improved network optimization algorithms
