Papers

Click this Icon for an Abstract. Or click here to show all abstracts.

Journal articles based on a (single) refereed conference version, are merged, and sorted based on the date of the more recent (journal) publication.

This is a Google-scholar profile for the purpose of citations (as my name appears in various forms on papers).

Multi-agent and Multivariate Submodular Optimization, with Richard Santiago, 2016.
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem, with A. Vetta, G.T. Wilfong, FOCS 2015.
Inapproximability of Single-Sink Unsplittable and Confluent Flows, with A. Vetta, 2015.
Co-Location-Resistant Clouds, with Y. Azar, S. Kamara, I. Menache, M. Raykova, ACM Cloud Computing Security Workshop 2014.
Maximum Edge-Disjoint Paths in k-Sums of Graphs, with C. Chekuri, G. Naves, ICALP 2013.
A Tight Lower Bound for Online Vector Bin Packing, with Y. Azar, I. Cohen, and S. Kamara, STOC 2013.
Shortest path versus Multi-hub Routing in Networks with Uncertain Demand, with A. Fr\'echette, M. Thottan, P. Winzer, To appear Transactions on Networking, Preliminary version in Infocom 2013.
The VPN Conjecture is True, with Navin Goyal and Neil Olver. Journal of the ACM, Vol. 60-3, (2013). Preliminary version in Symposium on Theory of Computing STOC 2008.
We want to build a network that can transport any demand matrix (Dij) where jDijbi. The bi's are called marginals - they simply indicate that the total demand (traffic) involving node i is at most bi. The class of all such matrices are called the hose matrices. We dont know or care who i will actually communicate with. In addition, we must route traffic "obliviously", which means that routing of traffic between nodes i and j does not depend on what other traffic there is in the network. In other words, our routing cannot adapt to congestion in the network: we must prespecify how any pair communicates regardless of which hose demand matrix we are given. Our goal is to find an oblivious routing such that the total capacity needed on the edges of the network is minimized. This is called the Virtual Private Network (VPN) problem. Fingerhut-Suri-Turner and Gupta-Kleinberg-Kumar-Rastogi-Yener showed that there is always a tree network whose total cost is within a factor of 2 of the minimum cost VPN. It was widely speculated and conjectured in Italiano-Leonardi-Oriolo, that there is always an optimal VPN which is a tree. We show this is true using pyramidal routing, a concept recently introduced by Grandoni-Kaibel-Oriolo-Skutella to attack the VPN problem.
The All-or-Nothing Multicommodity Flow Problem, with C. Chekuri, S. Khanna, Siam J. Computing, Vol. 42-4, (2013), pp 1467-1493. Preliminary version in Proceedings of STOC 2004.
The maximum edge-disjoint path problem (EDP) consist of a supply graph and some terminal pairs si,ti for i=1,2...,k. The goal is to find a maximum subset of the pairs that can be simultaneously satisfied by disjoint paths in the supply graph. Guruswami et al. (see below) showed that in directed graphs the maximum edge-disjoint path problem (EDP) is hard to polytime approximate to better than a factor of m.5-ε (where m is the number arcs and any ε>0). However similar hardness results were not known for the undirected version (it was only known to be hard to constant approximate). This paper studies a relaxation of EDP in undirected graphs, the all-or-nothing multicommodity flow problem, where one is only asked to find a subset of the pairs for which there is a flow satisfying their demands. The main result is that the integrality gap for this relaxation is at most a polylogarithmic factor (thus exponentially better than for directed graphs). Recently an almost matching polylogarithmic lower bound was found by Andrews and Zhang.
Flow-Cut Gaps for Integer and Fractional Multiflows, with C. Chekuri and C. Weibel. Journal of Combinatorial Theory, B., Vol. 103-2, (2013), pp 248-273. Prelimiary version in SODA 2010 .
Topology-Aware VM Migration in Bandwidth Oversubscribed Datacenter Networks, with N. Jain, I. Menache, S. Naor, ICALP 2012.
Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2, with L. S\'eguin-Charbonneau. Foundations of Computer Science, FOCS 2011.
Strategic network formation and local peering contracts. with E. Anshelevich, G. Wilfong. Games and Economic Behaviour, Vol. 73-1, (2011), pp 17-38. Preliminary version appeared in: Foundations of Computer Science, FOCS 2006.
We design a game-theoretic framework to analyze contracts between competing parties on the Internet, partly inspired by issues arising in interdomain routing.
Approximability of Robust Network Design, with N. Olver. To appear Mathematics of Operations Research. Preliminary version in: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
We show for the first time a class of (separable) demand polytopes for which the associated robust network design problem exhibits polylog hardness. We also show that for the class of demand polytopes induced by a tree (T-topes) there is an 8-approximate polytime algorithm (though this class of problems may possibly be in P).
Buy-at-Bulk Network Design with Protection with Chandra Chekuri, Spyros Antonakapoulos, and Lisa Zhang. Mathematics of Operations Research. (2011). Preliminary version in: Foundations of Computer Science FOCS 2007.
Dynamic vs Oblivious Routing in Network Design, with Navin Goyal and Neil Olver, Algorithmica Volume 61, pp. 161--173, (2011). 17th Annual European Symposium on Algorithms (ESA 2009).
Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular, we compare \emph{oblivious} routing, where the routing between each terminal pair must be fixed in advance, to \emph{dynamic} routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of BigΩ(log{n}) more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric hose model. This answers a question in \cite{chekurisurvey07}, and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design for single-sink traffic patterns~\cite{ChekuriHardness07}.
Single Sink Multicommodity Flow with Side Constraints. Chapter in: Research Trends in Combinatorial Optimization. William Cook, Laszlo Lovasz, Jens Vygen (Editors); Springer, Berlin 2009.
In recent years, several new models for network flows have been analyzed, inspired by emerging telecommunication technologies. These include models of {\em resilient flow}, motivated by the introduction of high capacity optical links, {\em coloured flow}, motivated by Wavelength-Division-Multiplexed optical networks, {\em unsplittable flow} motivated by SONET networks, and {\em confluent flow} motivated by next-hop routing in internet protocol (IP) networks. In each model, the introduction of new side-constraints means that a max-flow min-cut theorem does not necessarily hold, even in the setting where all demands are destined to a common node (sink) in the network. In such cases, one may seek bounds on the flow-cut gap'' for the model. Such approximate max-flow min-cut theorems are a useful measure for bounding the impact of new technology on congestion in networks whose traffic flows obey these side constraints.
Edge-disjoint paths in planar graphs with constant congestion with C. Chekuri, S. Khanna. SIAM J. Computing, Volume 39, Issue 1, pp. 281-301 (2009) (invited issue for STOC 2006.)
For planar graphs, we show that if each edge capacity is at least 4, then the natural LP for the maximum integral multicommodity flow problem has a constant integrality gap (as opposed to n if capacities are at most 1).
Approximate Integer Decompositions for Undirected Network Design Problems, with C. Chekuri, SIAM J. Discrete Math. Volume 23, Issue 1, pp. 163-177 (2008).
Degree-constrained network flows with P. Donovan, A. Vetta, G. Wilfong. Symposium on the Theory of Computation, STOC 2007.
We consider the single sink multicommodity flow problem where flow out of any node may use at most d arcs. If d=1, then such flows are called confluent; if d=2 we call such flows bifurcated. It was previously shown that confluent flows may have node congestion up to O(log(n)). We show that for d=2, this unbounded congestion gap disappears: we show that the congestion gap is at most 2 (and this is best possible). In order to better understand the trade-off between d=1 and d=2, we consider the β-confluent flow problem for β[0,1]. Here we require that a β fraction of the flow out of any node must exit on a single arc (and the remainder on possibly one other arc). We show that for any β[12,1), there is a β-confluent flow of congestion at most (1+β1-β).
Island hopping and path colouring, with applications to WDM network design with A. McGregor. Symposium on Discrete Algorithms, SODA 2007.
We study problems related to the design of transparent optical networks, where flow paths must also be assigned an end to end'' wavelength (colour). If, this is impossible, an expensive (OEO) conversion takes place. We try to partition the edges of a graph into transparent islands so that no demand has to hop between islands too often. In a different version, we show a simple fractional implies integral result for single source multicommodity multicoloured flow. This reduces the corresponding WDM network design problem to a single-source buy at bulk problem with single cable type, for which a 3.55 approximation is known (Hassin, Ravi, Salman).
A Note on Multiflows and Treewidth with C. Chekuri and S. Khanna. Algorithmica, Volume 54, Issue3, Page 400, 2009.
We introduce a noncooperative game in an effort to understand business relationships between entities (enterprises, ISPs, residential customers etc.) on the Internet. Contracts are local (ie bilateral) between two entities and may either be of a peer-to-peer or a customer-provider variety. Entities bid (or demand payment) for the formation of these contracts, and in the resulting network some traffic is routed and other traffic dropped; providers may incur a penalty if their customer's traffic is dropped. Stable solutions to this game may have some interesting properties, including lending of money with long-range effects (money trickles into the hands of distant entities having nothing to do with the customer who paid).
Selective Randomized Load Balancing and Mesh Networks with Changing Demands with P. Winzer. Journal of Optical Networking Vol. 5, Issue 5, pp. 320-339, 2006.
Design Tools for Transparent Optical Networks Chandra Chekuri, Paul Claisse, Rene Essiambre, Steven Fortune, Dan Kilper, Karun Nithi, Wonsuck Lee, Iraj Saniee, Bruce Shepherd, Gordon Wilfong, Chris White, Lisa Zhang. Bell Labs Technical Journal. Volume 11, Issue 2, 129-143, (2006)
An O(sqrt n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. with C. Chekuri, S. Khanna, Theory of Computing 2/7, pp. 137-146 (2006).
Hardness of Robust Network Design with C. Chekuri, G. Oriolo, M.G. Scutella, Networks, vol. 50, no. 1, (2007), 50-54. Preliminary version in: INOC 2005.
We are given an uncapacitated undirected graph G and a collection P of matrices for pairwise traffic demands between nodes of G. What is the cheapest assignment of edge capacity needed so that any matrix D in P can be routed using this capacity? In the "oblivious routing" setting, for each pair i,j there is a pre-specified unit flow ("template") and one may only scale this flow up or down according to the value of Dij. In this version Applegate and Cohen showed that the optimal capacity is computable in polytime. If we may choose our flows dynamically for each different demand matrix, then obviously we may need less capacity. We show, by a reduction from graph expansion, that this problem is hard, even for a single-source hose problem (and even to get within a factor 2).
Edge-Disjoint Paths in Planar Graphs, with C. Chekuri, S. Khanna, FOCS 2004 .
Garg, Vazarani and Yannakakis showed examples where the integrality gap (the natural formulation) for the maximum edge disjoint path problem (EDP) is as bad as n even for planar graphs. For planar graphs, we show that if each edge capacity is at least 2, then this integrality gap drops to log(n).
Lighting Fibers in a Dark Network, with Adrian Vetta, Journal on Selected Areas in Communication , Vol. 22, Number 9, 1583-1588, 2004.
The Demand Matching Problem, with A. Vetta Mathematics of Operations Research Vol. 32, No. 3, August 2007, pp. 563-578. Preliminary version in IPCO 2002.
We introduce the following problem. Given a graph G where each node v has a capacity b(v), and we are also given a set of edges F where each such fF also comes with an integer demand d(f) and weight w(f). A subset M of F is a demand matching if for each node, the total demand of M-edges incident to it is at most b(v). We study the natural IP formulation for this (NP hard) problem and find that its integrality gap lies between 2.5 and 3 for bipartite graphs, and between 3 and 3.5 for general graphs.
Directed Network Design Problems with Orientation Constraints with S. Khanna, S. Naor, To appear: SIAM Journal for Discrete Mathematics, vol. 19 (1), 245-57, 2005. (Preliminary version in: SODA '99, San Francisco, January 1999, )
Network design problems arising from supermodular set requirement functions have been well studied, as have orientation problems where one wishes to orient some undirected edges to satisfy some connectivity conditions. Motivated by the design of strongly connected networks, we consider (for the first time as far as we know) the problem of joint orientation and subset selection of edges/arcs. The main finding is that a classical result of Frank on intersecting supermodular functions extends very simply to the joint setting.
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.
Decompositions are described for visualizing when a set of arcs forms a dijoin. An elementary algorithm is given for finding a mincost dijoin that runs in O(n^2m) - matching the best running time due to Gabow. A number of questions are posed related to packing dijoins. One of these is that there exists a constant C such that in any weighted digraph whose minimum weight directed cut is of size k, there is a packing of Ck dijoins (into the weights). It is proved there is a half-integral such packing.
Multicommodity Demand Flow in a Tree and Packing Integer Programs , with C. Chekuri, M. Mydlarz; ACM Transactions on Algorithms (TALG), 3(3), 2007. (Preliminary version in: ICALP 2003 )
We consider the multicommodity all-or-nothing flow problem in a tree. We are given a tree with integer edge capacities u(e) and a set F of demand edges f=uv, each with an integer d(f). A subset of demands is routable if no edge capacity is violated after each demand sends d(f) units of flow between its endpoints. Special cases of this problem include when the tree is a single edge (knapsack problem), when the tree is a star (demand matching problem) and when all demands are 1 (integer multicommodity flow on a tree), or when the tree is a line (interval packing), and when the tree is a star (the b-matching problem). For the unit demand case, Garg, Vazarani and Yannakis gave a 2-approximation for the the maximum cardinality problem. We show that the integrality gap for the weighted (unit demand) case is at most 4. Following, Cheriyan, Jordan, and Ravi, we ask whether this can be brought down to 3/2 (thus generalizing Shannon's multigraph edge colouring result). Our result together with a technique of Kolliopoulos and Stein can then be used to show that for general demands, a gap of at most 48 holds (the first constant factor for this problem).
Cluster and Server Selection Using Passive Monitoring with M. Andrews, A. Srinivasan, P. Winkler, F. Zane, Infocom 2002
The Theta Body and Imperfection, Chapter in: Perfect Graphs: By Ramirez Alfonsion and Bruce Reed, Wiley and Sons Ltd., U.K. 2001
The main new result in this paper is a polytime algorithm to determine whether a graph is partitionable: i.e., for each node v, G-v is ω-colourable and α-clique-coverable, where α (resp. ω) is the size of a max stable set (resp. clique). We then speculate whether separation routines for partitionable inequalities could be practical for solving packing problem instances for dense 0,1 matrices?
Route Oscillations in I-BGP with A. Basu, L. Ong, A. Rasala, G. Wilfong, SIGCOMM 2002; an article
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.
These papers provide a formal study of the border gateway protocol (BGP) which has become the defacto standard for determining routes between different autonomous systems (i.e. organizations, or enterprises under a common administrative control). Within an AS, protocols based on finding shortest paths are used for route selection, and hence, like the Ford-Bellman algorithm, they are guaranteed to finally stabilize into shortest path trees to each destination. The same is not true for BGP since the nodes may order preferences on paths arbitrarily. The SIGCOMM paper proposes a change to the protocol which provably eliminates one of the reasons for instability observed in practice (due to MED attribute). The solution was presented to the IETF.
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.
Many coarse network designs are performed as follows. For each source-destination pair of nodes s,t with say D traffic demand between them, reserve D units of capacity on each link of a shortest s-t path in the network (topology). This reserved bandwidth is completely vulnerable, however, to any single link failure. This paper generalizes the shortest path problem to natural resilient path analogues. Several resilient (up to k failures) versions are discussed including the case where we must route traffic on a collection of disjoint paths. Here a simple algorithm is described for the fractional version, and a 114-approximation algorithm is described for the integer version. It is also shown that it is NP-hard to obtain a polytime (114-ε)-approximation algorithm, for any ε>0. The longer version contains more discussion of alternative network resilience and restoration strategies.
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 ).
It is shown how a couple of augmentation rules can be used to turn a multicommodity flow on a ring (cycle graph) into a minimum cost such flow. Such combinatorial algorithms for exact minimum cost multicommodity do not seem to exist, even in simple cases.
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)
It is shown that finding the maximum number of a given set of si,ti pairs that can be connected by arc-disjoint paths in a directed graph cannot be approximated (in polytime) even within a factor of m1/2-esπlon for any ε>0. On the positive side, we describe a factor m1/2 approximation achievable by a greedy algorithm even in the presence of arc capacities (a greedy such approximation was already known for unit capacities).
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.
Originally motivated by routing in a passive optical ring network, we consider the multicommodity flow problem in a node-capacitated ring. The cut condition is not sufficient to characterize solvability of such instances. We show, however, that it is sufficient to consider distance cut inequalities induced by 0,1,2 node weights. We also see that a fractionally routable set of demands can be integrally routed if we increase each node capacity by 1.
The graphs with all subgraphs t-perfect, with A.M.H. Gerards. Siam Journal of Discrete Mathematics, Vol. 11, No. 4, 1998, 524-545.
Given a 0,1 matrix A with two 1' per row, when is it the case that the Chvatal closure of the polytope {x:Ax1,x0} gives an integer polytope? This happens precisely when the rows of A determine a so-called t-perfect graph. No characterization of these graphs/matrices is known. This paper characterizes those graphs for which every subgraph is t-perfect. This extends earlier results on graphs with no K4 minor. Schrijver has since shown that the linear system for this class of graphs is also TDI (totaly dual integral).
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.
These two papers (the first empirical, the latter theoretical) argue that the cost of wavelength converters in a wavelength division multiplexed (WDM) network, is not warranted in static networks with large fiber capacities (represented as many parallel edges). Also discussed, is the phenomenon that colouring random instances of path intersection graphs is much easier in practice than colouring random instances of graphs.
Excluding minors in cubic graphs, with K. Kilakos. Combinatorics, Computing and Probability, vol. 3, 1996, 57-58.
We describe a decomposition for cubic graphs that contain no minor isomorphic to the Petersen Graph with one edge removed. This is used to show such graphs are 3-edge-colourable.
Applying Lehman's theorem to packing problems, Mathematical Programming, vol. 71, 1995, 353-366.
It is seen how a more general form of Lehman's theorem (only stated in Lehman's own paper on the topic, but whose proof follows directly from the Seymour and Padberg presentations) can be translated to obtain results for packing problems. In particular, this leads to a complete characterization of the stable set polytope for graphs G, such that G-N[v] is bipartite for each node v.
Subdivisions and the chromatic index of r-graphs, with K.Kilakos. Journal of Graph 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 graph is 4-critical if it is not 3-node colourable, but every proper subgraph is. Toft conjectured (197?) that every such graph had a subgraph which is obtained from K4 by subdividing each edge an even number of times. This conjecture could be viewed as the natural analogue to the fact that G is bipartite only if it has no odd cycle. We prove the conjecture in the case where such a graph has a node of degree 3 (this was the first partial result).
A note on clutter partitions, Operations Research Letters, vol. 15, 1994, 127-131.
Near-perfect matrices, Mathematical Programming, vol. 64, 1994, 295-323.
Even, Itai and Shamir showed that in undirected graphs the following 4-terminal edge-disjoint path (EDP) problem is NP-hard: do there exist k edge-disjoint paths, k' of which join terminals s1,t1, and k-k' of which join terminals s2,t2? A main consequence of this paper is that this problem is solvable for graphs on a fixed surface.

Schrijver gave a polytime method for determining the existence of disjoint paths between k terminal pairs for graphs embedded on a fixed surface and for fixed k. Schrijver's approach is to consider each homotopic pattern that the possible collections of disjoint paths may form. For each pattern, he then applies shifting techniques to see whether there is a solution to the problem. The number of homotopies required ostensibly grows exponentially (thus the reason for a fixed k). We show that even for non-fixed k, one may restrict to a polynomially bounded (in the size of the supply and demand graphs) number of homotopic patterns as long as the number of terminals is fixed.

Induced circuits in planar graphs, with C. McDiarmid, B. Reed, A. Schrijver. Journal of Combinatorial Theory (B), vol. 60, 1994, 169-176.
An algorithm is given to determine for a given planar graph and nodes s,t, the maximum number of s-t paths such that there is no edge joining internal nodes on distinct paths in the collection. For graphs on a fixed surface, and with k fixed, an algorithm is described to determine whether there exists such a collection of k paths. The fixed assumption can be dropped by applying the results from "Preselecting..." above.
Formulations for the stable set polytope , with W. Pulleyblank. Proceedings of Integer Programming and Combinatorial Optimization '93, Erice, Italy 1993).
Martin Grotschel in the early 1980's posed the following as one of the top outstanding questions in polyhedral combinatorics. Find a complete description for the stable set polytope of a claw-free graph (there is no stable set of size 3 in N(v) for each v). As every line graph is claw-free, such a system would generalize Edmonds Mathching Polyhedron Theorem. Despite attempts by many, such a result remains elusive. In this paper a description, and compact formulation, is given for graphs where for each v there is no stable set of size 3 amongst the nodes at distance 2 from v (called distance claw-free). This problem was solved in 2005! The solution came about from the work of Seymour-Chudnovsky and Eisenbrand-Oriolo-Stauffer-Ventura. It turned out that distance claw-free graphs formed a critical subclass in the solution.
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/5)n 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.