Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
From MaRDI portal
Publication:1373746
DOI10.1007/BF02614369zbMath0889.90150OpenAlexW2022163094WikidataQ57318275 ScholiaQ57318275MaRDI QIDQ1373746
Publication date: 25 November 1997
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02614369
Related Items (12)
Simplified group activity selection with group size constraints ⋮ A multiscale semi-smooth Newton method for optimal transport ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ Simple linear flow decomposition algorithms on trees, circles, and augmented trees ⋮ The inverse Voronoi problem in graphs. II: Trees ⋮ A network simplex method for the budget-constrained minimum cost flow problem ⋮ Heuristics for the dynamic facility location problem with modular capacities ⋮ Competitive location and pricing on a line with metric transportation costs ⋮ Fast algorithms for convex cost flow problems on circles, lines, and trees ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- Complexity models for incremental computation
- A polynomial time primal network simplex algorithm for minimum cost flows
- Updating a balanced search tree in 0(1) rotations
- A data structure for dynamic trees
- Organization and maintenance of large ordered indexes
- Finding Minimum-Cost Circulations by Successive Approximation
- Finding minimum-cost circulations by canceling negative cycles
- Biased Search Trees
- An Efficient Parallel Biconnectivity Algorithm
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Self-adjusting binary search trees
- A new approach to the maximum-flow problem
- Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
This page was built for publication: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
