Approximate Integer Decompositions for Undirected Network Design Problems, with C. Chekuri, Submitted.
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 )
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.
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.
Excluding minors in cubic graphs, with K. Kilakos. Combinatorics, Computing and Probability, vol. 3, 1996, 57-58.
Subdivisions and the chromatic index of r-graphs, with K.Kilakos. Journal of Graph Theory Theory, vol 22, 1996, 203-211
A note on a conjecture of Toft , with T.R. Jensen. Combinatorica, vol. 15, 1995, 373-377.
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.
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.