Hardness of Robust Network Design with Chandra Chekuri, Gianpaolo Oriolo, Maria Scutella, INOC 2005. .
Edge-Disjoint Paths in Planar Graphs, with C. Chekuri, S. Khanna, FOCS 2004 .
Approximate Integer Decompositions for Undirected Network Design Problems, with C. Chekuri, Submitted.
The All-or-Nothing Multicommodity Flow Problem,
with C. Chekuri, S. Khanna,
Proceedings of STOC 2004 .
(Note: an error in the congestion 1 algorithm
was corrected and a new draft will be posted).
Directed Network Design Problems with Orientation Constraints with S. Khanna, S. Naor, To appear: SIAM Journal for Discrete Mathematics, 2004. (Earlier version in: SODA '99, San Francisco, January 1999, )
Bipartite domination and Simultaneous Matroid Covers , with C.W. Ko, SIAM Journal for Discrete Mathematics, Vol. 16, No. 4, 517-523, 2003.
Visualizing, Finding and Packing Dijoins, with A. Vetta, Chapter in: Graph Theory and Combinatorial Optimization, GERAD 25th Anniversary Volumes, Springer 2005.
The Demand Matching Problem, with A. Vetta IPCO 2002
Multicommodity Demand Flow in a Tree and Packing Integer Programs, with C. Chekuri, M. Mydlarz, Submitted 2003; (Earlier version in: ICALP 2003 )
A Fast and Scaleable Approximation Algorithm for Computing Shared Recovery Flows Minimizing Long-Term Expected Cost with L. Fleischer, A. Meyersen, I. Saniee, A. Srinivasan, CORC Report 2003-10
The Theta Body and Imperfection, Chapter in: Perfect Graphs: By Ramirez Alfonsion and Bruce Reed, Wiley and Sons Ltd., U.K. 2001
Some strategies for reserving resilient capacity, with G. Brightwell, G. Oriolo. SIAM J. Discrete Math., , Vol. 14, No. 4, 524-539, 2001. A fuller, earlier version describes a number of alternative strategies for different types of restoration architectures.
Reserving Resilient Capacity for a Single Commodity with Upper Bound Constraints with G. Brightwell, G. Oriolo. Networks, vol 41. no.2 (2003), pp 87-96.
An Augmentation Algorithm for Mincost Multicommodity Flow on a Ring, with Lisa Zhang. Discrete Applied Mathematics 110, 2001, 301-315 (also Globecomm '99, High Speed Networks, Rio de Janeiro, Brazil,Dec. 99 ).
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems, with Venkat Guruswami, Sanjeev Khanna, Raj Rajaraman, Mihalis Yannakakis. Journal of Computer and System Sciences, Volume 67, Issue 3, Nov. 2003, Pages 473-652. (also in Proc. 31st Annual ACM Symposium on Theory of Computing (STOC) , pp. 19-28, 1999)
Node-capacitated multicommodity routing for a ring, , with V. Tandon, A. Frank, Z. Vegh. Math. of Operations Research , Vol. 27, No. 2, May 2002, 372-383.
Induced circuits in planar graphs, with C. McDiarmid, B. Reed, A. Schrijver. Journal of Combinatorial Theory (B), vol. 60, 1994, 169-176.
Preselecting homotopies for the weighted disjoint paths problem,
with A.M.H. Gerards.
manuscript, 1993,
Schrijver gave a general method for finding collections of $k$ disjoint paths in graphs embdedded on
a fixed surface. His approach is to consider each possible homotopic pattern that such paths may form.
He then applies shifting techniques to see whether there is a solution to the problem with that homotopy.
The number of homotopies required ostensibly grows exponentially (thus the reason for a fixed $k$ in (*)).
Here we show that one may restruct to a polynomially bounded (in the size of the graph) number of homotopic patterns
in searching for such a collection of paths.