Concepedia

Primal-dual approximation algorithms for integral flow and multicut in trees

Naveen Garg, Vijay V. Vazirani, Mihalis Yannakakis

Algorithmica · 1997 · 377 citations · 26 references

DOI

Concepts

References

26

Approximation Algorithms for NP-Hard Problems

Dorit S. Hochba · ACM SIGACT News · 1997 · 3.1K citations · Full text

, , +13

Optimization, approximation, and complexity classes

Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1991 · 1.7K citations

, , +12

Proof verification and the hardness of approximation problems

Sanjeev Arora, Carsten Lund, Rajeev Motwani et al. · Journal of the ACM · 1998 · 1.4K citations · Full text

, , +14

Graph Minors .XIII. The Disjoint Paths Problem

Neil Robertson, Paul Seymour · Journal of Combinatorial Theory Series B · 1995 · 1.3K citations

, , +8

On the Complexity of Timetable and Multicommodity Flow Problems

Shimon Even, Alon Itai, Adi Shamir · SIAM Journal on Computing · 1976 · 1.1K citations

, , +16