%% ToC#241 v002/a007.bib   Chekuri, Khanna, Shepherd


@inproceedings{AndrewsCKZ05,
 author    = {Matthew Andrews and
              Julia Chuzhoy and
              Sanjeev Khanna and
              Lisa Zhang},
 title     = {Hardness of the Undirected Edge-Disjoint Paths Problem with
              Congestion},
 booktitle = {Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)},
 year      = {2005},
 pages     = {226--244},
 eprint="focs:10.1109/SFCS.2005.41"
}

@article{AzarR06,
 author    = {Yossi Azar and
              Oded Regev},
 title     = {Combinatorial Algorithms for the Unsplittable Flow Problem},
 journal   = {Algorithmica},
 volume    = {44},
 number    = {1},
 year      = {2006},
 pages     = {49--66},
 note     =  {Preliminary version in {\em Proc.\ of IPCO}, 2001},
 eprint="algorithmica:yl21u55g402h8033,ipco:eq2xun7jtdm8udue"
}

@article{BavejaS00,
 author    = {Alok Baveja and
              Aravind Srinivasan},
 title     = {Approximation Algorithms for Disjoint Paths and Related
              Routing and Packing Problems},
 journal   = {Math. Oper. Res.},
 volume    = {25},
 number    = {2},
 year      = {2000},
 pages     = {255--280},
 pdf="http://www.cs.umd.edu/~srin/PDF/edge-dis.pdf"
}

@inproceedings{edp_revisited,
 author    = {Chandra Chekuri and 
              Sanjeev Khanna},
 title     = {Edge disjoint paths revisited},
 booktitle = {Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
 year      = {2003},
 pages     = {628--637},
 eprint="soda:644108.644212"
}

@inproceedings{allnothing,
 author    = {Chandra Chekuri and 
              Sanjeev Khanna and 
              F. Bruce Shepherd},
 title     = {The all-or-nothing multicommodity flow problem},
 booktitle =  {Proceedings of the 36th Annual ACM Symposium on Theory of
              Computing (STOC)},
 year      = {2004},
 pages     = {156--165},
 eprint="stoc:1007352.1007383"
}

@inproceedings{ChekuriMS03,
 author    = {Chandra Chekuri and 
              Marcelo Mydlarz and 
              F. Bruce Shepherd},
 title     = {Multicommodity Demand Flow in a Tree},
 booktitle = {Proceedings of 30th International
              Colloquium on Automata, Languages and Programming (ICALP)},
 year      = {2003},
 pages     = {410--425},
 publisher = {Springer},
 series    = {Lecture Notes in Computer Science},
 volume    = {2719},
 eprint="icalp:du648d9x5721adll"
}

@InCollection{Frank_survey,
 author =       {Andr\'{a}s Frank},
 title =        {Packing paths, cuts, and circuits - a survey},
 booktitle =    {Paths, Flows and VLSI-Layout},
 pages =        {49--100},
 publisher = {Springer Verlag},
 year =         {1990},
 editor =       {B.~Korte and L.~Lov\'{a}sz and H.~J.~Pr\"{o}mel
and A.~Schrijver},
}

@article{GargVY97,
 author    = {Naveen Garg and
              Vijay V. Vazirani and
              Mihalis Yannakakis},
 title     = {Primal-Dual Approximation Algorithms for Integral Flow and
              Multicut in Trees},
 journal   = {Algorithmica},
 volume    = {18},
 number    = {1},
 year      = {1997},
 pages     = {3--20},
 eprint="algorithmica:x1dykd3030ggac4w"
}

@article{GuruswamiKRSY03,
 author    = {Venkatesan Guruswami and
              Sanjeev Khanna and
              Rajmohan Rajaraman and
              F. Bruce Shepherd and
              Mihalis Yannakakis},
 title     = {Near-optimal hardness results and approximation algorithms
              for edge-disjoint paths and related problems},
 journal   = {J. Comput. Syst. Sci.},
 volume    = {67},
 number    = {3},
 year      = {2003},
 pages     = {473--496},
 note      = {Preliminary version in {\em Proc.\ of ACM STOC}, 1999},
 eprint="jcss:10.1016/S0022-0000(03)00066-7,stoc:301250.301262"
}

@PhdThesis{Kleinberg-thesis,
 author =       {Jon Kleinberg},
 title =        {Approximation algorithms for disjoint paths problems},
 school =       {MIT},
 year =         {1996},
 address =      {Cambridge, MA},
 month =        {May},
}


@InCollection{Kolliopoulos_survey,
 author =       {Stavros Kolliopoulos},
 title =        {Edge Disjoint Paths and Unsplittable Flow},
 booktitle =    {Handbook on Approximation Algorithms and Metaheuristics},
 publisher = {Chapman and Hall},
 editor =       {Teofilo F. Gonzalez},
 series =       {CRC Computer and Information Science},
 year =         {2006},
 note =         {To appear.},
}

@article{KolliopoulosS04,
 author    = {Stavros G. Kolliopoulos and
              Clifford Stein},
 title     = {Approximating disjoint-path problems using packing integer
              programs},
 journal   = {Math. Program.},
 volume    = {99},
 number    = {1},
 year      = {2004},
 pages     = {63--87},
 note      = {Preliminary version in {\em Proc.\ of IPCO, 1998}},
 eprint="mathprog:lh5yrd3peyp3kb3h,ipco:upy56mcmrvfqdm84"
}

@article{Kolman03,
 author    = {Petr Kolman},
 title     = {A note on the greedy algorithm for the unsplittable flow
              problem},
 journal   = {Inf. Process. Lett.},
 volume    = {88},
 number    = {3},
 year      = {2003},
 pages     = {101--105},
 eprint="ipl:10.1016/S0020-0190(03)00351-X"
}

@inproceedings{KolmanS02,
 author    = {Petr Kolman and
              Christian Scheideler},
 title     = {Improved bounds for the unsplittable flow problem},
 booktitle = {Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA)},
 year      = {2002},
 pages     = {184--193},
 eprint="soda:545381.545404"
}

@article{MaW00,
 author    = {Bin Ma and
              Lusheng Wang},
 title     = {On the Inapproximability of Disjoint Paths and Minimum Steiner
              Forest with Bandwidth Constraints},
 journal   = {J. Comput. Syst. Sci.},
 volume    = {60},
 number    = {1},
 year      = {2000},
 pages     = {1--12},
 eprint="jcss:10.1006/jcss.1999.1661"
}

@Unpublished{Nguyen05,
 author =       {Thanh Nguyen},
 title =        {On Disjoint Paths},
 note =         {Personal communication},
 month =        {August},
 year =         {2005},
}


@Book{Schrijver_book,
 author =       {Alexander Schrijver},
 title =        {Combinatorial Optimization: Polyhedra and Efficiency},
 publisher =    {Springer-Verlag},
 address   =    {Berlin Hiedelberg},
 year =         {2003},
}

@inproceedings{KasturiV04,
 author    = {Kasturi R. Varadarajan and
              Ganesh Venkataraman},
 title     = {Graph decomposition and a greedy algorithm for edge-disjoint
              paths},
 booktitle = {Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA)},
 year      = {2004},
 pages     = {379--380},
 eprint="soda:982792.982846"
}