Trans-dichotomous algorithms for minimum spanning trees and shortest paths
From MaRDI portal
Recommendations
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- An optimal minimum spanning tree algorithm
- A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
- Computational Methods for Minimum Spanning Tree Algorithms
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
Cites work
- Design and implementation of an efficient priority queue
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Faster algorithms for the shortest path problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- Hash functions for priority queues
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- Linear verification for spanning trees
- Surpassing the information theoretic bound with fusion trees
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
Cited in
(54)- Fusion trees can be implemented with AC^0 instructions only
- On constructing the elimination tree
- Iterated nearest neighbors and finding minimal polytopes
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Space-efficient indexes for forbidden extension queries
- Validating the Knuth-Morris-Pratt failure function, fast and online
- Lower bounds for dynamic algebraic problems
- All-pairs shortest paths and the essential subgraph
- Shortest paths algorithms: Theory and experimental evaluation
- Distributed verification of minimum spanning trees
- Color-spanning localized query
- Faster compressed quadtrees
- Data structures for categorical path counting queries
- From regular expression matching to parsing
- Input-output networks offer new insights of economic structure
- Universal reconstruction of a string
- \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm
- Proof labeling schemes
- Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
- Improved algorithms for replacement paths problems in restricted graphs
- Rectilinear paths among rectilinear obstacles
- Linear-space data structures for range frequency queries on arrays and trees
- Efficient range searching for categorical and plain data
- An optimal \(O(N^{2})\) algorithm for computing the min-transitive closure of a weighted graph
- Dynamic Planar Range Maxima Queries
- FAST ALGORITHMS FOR 3-D DOMINANCE REPORTING AND COUNTING
- Computational Methods for Minimum Spanning Tree Algorithms
- Submatrix maximum queries in Monge matrices are equivalent to predecessor search
- Universal reconstruction of a string
- An optimal parallel algorithm for minimum spanning trees in planar graphs
- Path Minima in Incremental Unrooted Trees
- On compressing permutations and adaptive sorting
- Cross-document pattern matching
- scientific article; zbMATH DE number 60387 (Why is no real title available?)
- Finding the k Shortest Paths
- The saga of minimum spanning trees
- Using sparsification for parametric minimum spanning tree problems
- Smoothing the Gap Between NP and ER
- From Regular Expression Matching to Parsing
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Trans-dichotomous algorithms without multiplication — some upper and lower bounds
- Partitioned event graph: formalizing LP-based modelling of parallel discrete-event simulation
- Random access to grammar-compressed strings and trees
- A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
- Faster shortest-path algorithms for planar graphs
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- scientific article; zbMATH DE number 7765406 (Why is no real title available?)
- Random access in persistent strings and segment selection
- Directed shortest paths via approximate cost balancing
- Space-efficient B trees via load-balancing
- Algorithm 1052: evaluating a Boolean polynomial on all possible inputs
- A fast algorithm for data collection along a fixed track
- Well-separated pair decomposition in linear time?
- A faster algorithm for the single source shortest path problem with few distinct positive lengths
This page was built for publication: Trans-dichotomous algorithms for minimum spanning trees and shortest paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329156)
