Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
From MaRDI portal
Publication:1373746
DOI10.1007/BF02614369zbMATH Open0889.90150DBLPjournals/mp/Tarjan97OpenAlexW2022163094WikidataQ57318275 ScholiaQ57318275MaRDI QIDQ1373746FDOQ1373746
Authors: Robert E. Tarjan 
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
Recommendations
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- scientific article; zbMATH DE number 3904297
- Exact and heuristic algorithms for dynamic tree simplification
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- Dynamic algorithms for graphs of bounded treewidth
- Dynamic algorithms for graphs of bounded treewidth
- scientific article; zbMATH DE number 4060712
- Improving TSP Tours Using Dynamic Programming over Tree Decompositions
Cites Work
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- A polynomial time primal network simplex algorithm for minimum cost flows
- A data structure for dynamic trees
- Title not available (Why is that?)
- Finding Minimum-Cost Circulations by Successive Approximation
- Self-adjusting binary search trees
- A new approach to the maximum-flow problem
- An Efficient Parallel Biconnectivity Algorithm
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Title not available (Why is that?)
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Finding minimum-cost circulations by canceling negative cycles
- A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
- Organization and maintenance of large ordered indexes
- Biased Search Trees
- Updating a balanced search tree in 0(1) rotations
- Complexity models for incremental computation
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- Title not available (Why is that?)
- Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (20)
- Simple linear flow decomposition algorithms on trees, circles, and augmented trees
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Simplified group activity selection with group size constraints
- A polynomial time primal network simplex algorithm for minimum cost flows
- A network simplex method for the budget-constrained minimum cost flow problem
- Multiscale strategies for computing optimal transport
- The inverse Voronoi problem in graphs. II: Trees
- A multiscale semi-smooth Newton method for optimal transport
- Batch-parallel Euler tour trees
- Heuristics for the dynamic facility location problem with modular capacities
- A Data Structure for Dynamically Maintaining Rooted Trees
- Power balance and apportionment algorithms for the United States Congress
- Fast algorithms for convex cost flow problems on circles, lines, and trees
- Improved algorithms for the multicut and multiflow problems in rooted trees
- Competitive location and pricing on a line with metric transportation costs
- Dynamic trees in practice
- Title not available (Why is that?)
- Dynamic expression trees
- Self-adjusting top trees
This page was built for publication: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1373746)
