Improved algorithms for the multicut and multiflow problems in rooted trees
From MaRDI portal
Publication:1024699
DOI10.1007/s11750-007-0037-9zbMath1170.90470OpenAlexW2145330271MaRDI QIDQ1024699
Publication date: 17 June 2009
Published in: Top (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11750-007-0037-9
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Totally balanced and totally unimodular matrices defined by center location problems
- Improved complexity bounds for location problems on the real line
- On a class of balanced hypergraphs
- Finding level-ancestors in trees
- Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
- Polynomial time algorithms for 2-edge-connectivity augmentation problems
- Inapproximability and a polynomially solvable special case of a network improvement problem.
- A data structure for dynamic trees
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Doubly lexical ordering of dense 0--1 matrices
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- Fast Algorithms for Finding Nearest Common Ancestors
- Optimizing over Consecutive 1's and Circular 1's Constraints
- Totally-Balanced and Greedy Matrices
- Doubly Lexical Orderings of Matrices
- Self-adjusting binary search trees
- Three Partition Refinement Algorithms
- Recursive Star-Tree Parallel Data Structure
- Complexity of Monotone Networks for Computing Conjunctions