Abstract The Projection Median of a Set of Points in R 2 (2009)
Stephane Durocher, David Kirkpatrick
We define the projection median of a non-empty and finite multiset of points in R 2. We show the projection median provides a better approximation of the Euclidean (ℓ2) median than do the...
Biedl, Therese, Durocher, Stephane, Hoos, Holger H., Luan, Shuang, Saia, Jared, Young, Maxwell
he segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes...
D.: Bounded-velocity approximations of mobile Euclidean 2-centres (2008)
Stephane Durocher, David Kirkpatrick
A Euclidean 2-centre of a finite and nonempty set of points P in R 2 is a set of two points, denoted Ξ(P) = {ξ1(P), ξ2(P)}, that minimizes the maximum Euclidean (ℓ2) distance from any point p in...
D.: Bounded-velocity approximations of mobile Euclidean 2-centres (2008)
Stephane Durocher, David Kirkpatrick
Communicated by (Name) Given a set P of points (clients) in the plane, a Euclidean 2-centre of P is a set of two points (facilities) in the plane such that the maximum distance from any client to its...
Kinetic Maintenance of Mobile k-Centres on Trees (2008)
Stephane Durocher, Christophe Paul
Abstract. Let C denote a set of n mobile clients, each of which follows a continuous trajectory on a weighted tree T. We establish tight bounds on the maximum relative velocity of the 1-centre and...
Balancing Traffic Load Using One-Turn Rectilinear Routing (2008)
Stephane Durocher, Evangelos Kranakis, Danny Krizanc, Lata Narayanan
Abstract. We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region and the origins and destinations correspond to pairs of points in that...
\Oh what a tangled web we weave..." (2007)
Alex Brodsky, Stephane Durocher, Ellen Gethner, Sir Walter Scott
The rectilinear crossing number of a graph G is the minimum number of edge crossings that can occur in any drawing of G in which the edges are straight line segments and no three vertices are...
1 Finding an Optimal Routing Policy on Simple Client-Server Models (2007)
We examine the problem of finding an optimalpolicy in routing single-connection calls between a client and a server on simple models of connection networks. We study the graphs K 2;2, K 5 andK 3;3...
L.: On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks (2007)
Stephane Durocher, David Kirkpatrick, Lata Narayanan
Abstract. We study routing algorithms for three-dimensional ad hoc networks that guarantee delivery and are k-local, i.e., each intermediate node v’s routing decision only depends on knowledge of...
Towardth rectilinear crossing number of K_n: new drawings, upper bounds, and asymptotics (2003)
Alex Brodsky, Stephane Durocher, Ellen Gethner
Sch;u;u;u and Wilf (Amer.Math Monthu 101 (1994) 939) assertthe "an important open problem in th study ofgraph embeddings is to determineth rectilinear crossing number of th K n ". A...
The rectilinear crossing number of K10 is 62 (2001)
Alex Brodsky, Stephane Durocher, Ellen Gethner
“Oh what a tangled web we weave...”
Toward the Rectilinear Crossing Number of $K_n$: New Drawings, Upper Bounds, and Asymptotics (2000)
Brodsky, Alex, Durocher, Stephane, Gethner, Ellen
Scheinerman and Wilf (1994) assert that `an important open problem in the study of graph embeddings is to determine the rectilinear crossing number of the complete graph K_n.' A rectilinear drawing...
The Rectilinear Crossing Number of K_10 is 62 (2000)
Brodsky, Alex, Durocher, Stephane, Gethner, Ellen
A drawing of a graph G in the plane is said to be a rectilinear drawing of G if the edges are required to be line segments (as opposed to Jordan curves). We assume no three vertices are collinear....
Toward the Rectilinear Crossing Number of K n : New Embeddings, Upper Bounds, and Asymptotics (2000)
Alex Brodsky, Stephane Durocher, Ellen Gethner
Scheinerman and Wilf [SW94] assert that "an important open problem in the study of graph embeddings is to determine the rectilinear crossing number of the complete graph Kn ." A rectilinear...
The Rectilinear Crossing Number of K_10 is 62 (2000)
Alex Brodsky, Stephane Durocher, Ellen Gethner, Sir Walter Scott
A drawing of a graph G in the plane is said to be a rectilinear drawing of G if the edges are required to be line segments (as opposed to Jordan curves). We assume no three vertices are collinear....
Finding an Optimal Routing Policy on Simple Client-Server Models (1999)
We examine the problem of finding an optimalpolicy in routing single-connection calls between a client and a server on simple models of connection networks. We study the graphs, and with respect to...