List of PapersMultilateral Transport Games with Gordon Wilfong, INOC 2005. .
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.
Content Distribution for Seamless Transmission, with E.G. Coffman, A. Constantinides, D. Rubenstein, D. Stavrou, Mathematical performance Modeling and Analysis, MAMA 2004 .
Lighting Fibers in a Dark Network, with Adrian Vetta, Journal on Selected Areas in Communication , Vol. 22, Number 9, 1583-1588, 2004.
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 )
Cluster and Server Selection Using Passive Monitoring with M. Andrews, A. Srinivasan, P. Winkler, F. Zane, Infocom 2002
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
Route Oscillations in I-BGP
with A. Basu, L. Ong, A. Rasala, G. Wilfong,
SIGCOMM 2002;
article describing this work
The Stable Paths Problem and Interdomain Routing
with T.G. Griffin, G.T. Wilfong.
IEEE/ACM Transactions on Networking,
vol. 10 (2), 2002, 232-243.
Policy Disputes in Path-Vector Protocols,
(Earlier version)
International Conference on Network Protocols, ICNP '99
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.
The graphs with all subgraphs t-perfect, with A.M.H. Gerards. Siam Journal of Discrete Mathematics, Vol. 11, No. 4, 1998, 524-545.
Strong orientations without even directed circuits, with A.M.H. Gerards. Discrete Mathematics, vol. 188, 1998, 111-125.
Face extensions in planar cubic graphs , with K. Kilakos. Discrete Mathematics, vol. 181, 1998, 179-191.
The Gallai-Younger Conjecture holds for planar graphs , with B.Reed. Combinatorica, vol. 16, 1996, 555-566.
Routing and configuration of static path optical transport networks , with E.Lowe, N. Walker. IEE Electronic Letters, vol. 32, 1996, 1913-1914.
Excluding minors in cubic graphs, with K. Kilakos. Combinatorics, Computing and Probability, vol. 3, 1996, 57-58.
Applying Lehman's theorem to packing problems, Mathematical Programming, vol. 71, 1995, 353-366.
Subdivisions and the chromatic index of r-graphs, with K.Kilakos. Journal of Graph Theory Theory, vol 22, 1996, 203-211
Right angle free subsets in the plane, with A. Gamble, W. Pulleyblank, B. Reed. Graphs and Combinatorics, vol. 11, 1995, 121-129.
A note on a conjecture of Toft , with T.R. Jensen. Combinatorica, vol. 15, 1995, 373-377.
A note on clutter partitions, Operations Research Letters, vol. 15, 1994, 127-131.
Near-perfect matrices, Mathematical Programming, vol. 64, 1994, 295-323.
Induced circuits in planar graphs, with C. McDiarmid, B. Reed, A. Schrijver. Journal of Combinatorial Theory (B), vol. 60, 1994, 169-176.
Formulations for the stable set polytope , with W. Pulleyblank. Proceedings of Integer Programming and Combinatorial Optimization '93, Erice, Italy 1993).
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.
On splitable sets, with W. Pulleyblank, B. Reed. Graph Theory Notes of New York XXIII, Eds. J.W. Kennedy, Louis V. Quintas, New York Academy of Sciences 1992, 11-20.
Non-interfering network flows, with C.McDiarmid, B. Reed, A.Schrijver. Scandinavian Workshop on Algorithm Theory (SWAT 92), Helsinki, July 8-10, 1992.
Hamiltonicity in claw-free graphs, Journal of Combinatorial Theory (B) vol. 53, 1991, 173-194.
Domination in graphs with minimum degree two,
with W. McCuaig.
Journal of Graph Theory,
vol. 13,
1989, 749-762.
We show that if a graph has minimum degree at least 2, and it is not one of 7 exception graphs,
then there exists a subset of $S$ of at most $2/5n$ nodes such that each node of $V-S$ is adjacent
to some node of $S$.
Domination parameters for the bishops graph,
with E.J. Cockayne and A.B. Gamble.
Discrete Mathematics
vol. 58,
1986, 221-227.
We answer a question from `Open problems in number theory' by Richard Guy.
How many bishops are needed on an n by n chessboard to make sure that each
square can be attacked by one of them?
An upper bound for the k-domination number of a graph, with E.J. Cockayne and A.B. Gamble. Journal of Graph Theory vol. 9, 1985, 533-534.
Domination of chessboards by queens on a column, with E.J. Cockayne and A.B. Gamble. Ars Combinatoria vol. 19, 1985, 105-118.