Improved algorithms for the multicut and multiflow problems in rooted trees

DOI10.1007/s11750-007-0037-9zbMath1170.90470OpenAlexW2145330271MaRDI QIDQ1024699

J. Martínez

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

zbMATH Keywords

rooted treestotally balanced matricesgreedy matricesmaximum integral multiflowsminimum multicuts

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

The ordered capacitated facility location problem

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