Improved algorithms for the multicut and multiflow problems in rooted trees

DOI10.1007/S11750-007-0037-9MaRDI QIDQ1024699zbMATH OpenOpenAlexFDO

Authors 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

greedy matricesmaximum integral multiflowsminimum multicutsrooted treestotally balanced matrices

Mathematics Subject Classification ID

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

Recommendations

• A greedy algorithm for multicut and integral multiflow in rooted trees
• Multicuts and integral multiflows in rings
• Multiway cut and integer flow problems in trees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• scientific article; zbMATH DE number 6861995

Cites work

• A data structure for dynamic trees
• A greedy algorithm for multicut and integral multiflow in rooted trees
• Complexity of Monotone Networks for Computing Conjunctions
• Doubly lexical ordering of dense 0--1 matrices
• Doubly Lexical Orderings of Matrices
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding level-ancestors in trees
• scientific article; zbMATH DE number 9246 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• Improved complexity bounds for location problems on the real line
• Inapproximability and a polynomially solvable special case of a network improvement problem.
• On a class of balanced hypergraphs
• Optimizing over Consecutive 1's and Circular 1's Constraints
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Recursive Star-Tree Parallel Data Structure
• Self-adjusting binary search trees
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Three Partition Refinement Algorithms
• Totally balanced and totally unimodular matrices defined by center location problems
• Totally-Balanced and Greedy Matrices

Cited in

(4)

• A greedy algorithm for multicut and integral multiflow in rooted trees
• scientific article; zbMATH DE number 6861995 (Why is no real title available?)
• The ordered capacitated facility location problem
• Improved parameterized and exact algorithms for cut problems on trees

This page was built for publication: Improved algorithms for the multicut and multiflow problems in rooted trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024699)