Abstract Empirical Evaluation of Randomly-Wired Multistage Networks (Extended Abstract) (2009)
Tom Leighton, Derek Lisinski, Bruce Maggs
In this paper, we present experimental data indicat-ing that multistage interconnection networks with ran-domly positioned wires are likely to be substantially better for message routing applications...
Multicommodity Flow and Circuit Switching Abstract (2008)
Given a set of request pairs in a network, the problem of routing virtual circuits with low congestion is to connect each pair by a path so that few paths use the same link in the network. We build...
Oblivious Routing on Node-Capacitated and Directed Graphs ∗ (2008)
Mohammad Thagi, Hajiaghayi Robert, D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke [18], and this work has led to many subsequent improvements and applications. Comparatively little is known...
Abstract On the Design of Reliable Boolean Circuits that Contain (2008)
Dan Kleitman, Tom Leighton, Yuan Ma
Partially Unreliable Gates* We investigate a model of gate failure for Boolean circuits in which a faulty gate is restricted to out-put one of its input values. For some types of gates, the model...
Abstract Improved Lower and Upper Bounds for Universal TSP in Planar Metrics (2008)
Mohammad T. Hajiaghayi, Robert Kleinberg, Tom Leighton
A universal TSP tour of a metric space is a total ordering of the points of the space such that for any finite subset, the tour which visits these points in the given order is not too much longer...
Steven Butler, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton
Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat they are wearing by looking at the colors of the...
Mohammadtaghi Hajiaghayi, Tom Leighton
the max-flow min-cut ratio for directed multicommodity flows
Steve Butler, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton
Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat they are wearing by looking at the colors of the...
Abstract Semi-oblivious Routing: Lower Bounds (2008)
Mohammadtaghi Hajiaghayi, Robert Kleinberg, Tom Leighton
We initiate the study of semi-oblivious routing, a relaxation of oblivious routing which is first introduced by Räcke and led to many subsequent improvements and applications. In semi-oblivious...
This paper provides an analysis of a natural k-round tournament over n = 2 k players, and demonstrates that the tournament possesses a surprisingly strong ranking property. The ranking property of...
Nabil Kahale, Tom Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel
7 We establish a lower bound of (1:12 \Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more...
N Barrier, Tom Leighton, Yuan Ma, C. Greg Plaxton
In this paper, we study the problem of constructing a sorting circuit, network, or PRAM algorithm that is tolerant to faults. For the most part, we focus on fault patterns that are random, i.e.,...
Division in O(log n) Depth Using O(...) Processors (2007)
: Improving a result by Beame, Cook and Hoover we construct a family of Puniform O( 1 ffl 2 log n) depth circuits for division with size O(n 1+ffl ) for any ffl ? 0. The key improvement is that we...
Markus Jakobsson, Tom Leighton, Michael Szydlo
Abstract. We introduce a technique for traversal of Merkle trees, and propose an e#cient algorithm that generates a sequence of leaves along with their associated authentication paths. For one choice...
Spanish Ministry of Education. (2007)
Matthew Andrews, Baruch Awerbuch, Antonio Fern, Jon Kleinberg, Tom Leighton, Zhiyong Liu, ...
Foundation, Hong Kong.
Containment Properties of Product and Power Graphs Antonio Fernandez a (2007)
In this paper we study containment properties of graphs in relation with the Cartesian product operation. We show that the isomorphism of two Cartesian powers G r
Matthew Andrews T, Antonio Fernandez, Mot Harchol-balter, Lisa Zhangl, Tom Leighton
A central issue in the design of modern communication networks is that of providing pe:formance guarantees. This issue is particularly important if the networks support real-time traffic such as...
Matthew Andrews, Mor Harchol-balter, Tom Leighton, Lisa Zhang
A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as...
Tom Leighton, Derek Lisinski, Bruce Maggs
In this paper, we present experimental data indicating that multistage interconnection networks with randomly positioned wires are likely to be substantially better for message routing applications...
Tom Leighton, Chi-jen Lu, Satish Rao
Abstract. The Lov'asz Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and...
Donald D. Chinn, Tom Leighton, Martin Tompa
Foundation under Grants CCR-9002891 and CCR-9301186. An adaptive routing algorithm is one in which the path a packet takes from its source to its destination may depend on other packets it...
Compression Using Ecient Multicasting (2007)
Many multiprocessor systems have the ability to broadcast and/or multicast information eciently. However, this ability is often overlooked when designing algorithms for these systems. In this paper,...
Parallel and Distributed Computing Combinatorial Algorithms (2006)
The first methods for tolerating more than a small number of worst- case faults in commonly-Lised networks such as the butterfly, the mesh of trees, and other hypercubic networks. Previously, work on...
New lower bounds for oblivious routing in undirected graphs (2006)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an...
New lower bounds for oblivious routing in undirected graphs (2006)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an...
New lower bounds for oblivious routing in undirected graphs (2006)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. Räcke showed that there is an...
In this paper, we consider a multicommodity flow problem where for each pair of vertices, (u.v), we are required to send f half-units of commodity (u,v) from u to v and f half-units of commodity...
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke [17], and this work has led to many subsequent improvements and applications. Comparatively little is known...
Online client-server load balancing without global information (2005)
Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton
We consider distributed online algorithms tbr maximizing through-put in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not...
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammadtaghi Hajiaghayi, Robert D. Kleinberg, Harald Räcke, Tom Leighton
Oblivious routing algorithms for general undirected networks were introduced by Räcke [Räcke 2002], and this work has led to many subsequent improvements and applications. Comparatively little is...
Online client-server load balancing without global information (2005)
Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert Kleinberg, Tom Leighton
We consider distributed online algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not...
Online client-server load balancing without global information (2005)
Baruch Awerbuch, Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton
We consider distributed online algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not...
Mohammadtaghi Hajiaghayi, Advisors Erik, D. Demaine, Tom Leighton, Naomi Nishimura, Summer Students
Email is the fastest and the most reliable way of contacting me.
Oblivious routing on node-capacitated and directed graphs (2005)
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Räcke
Oblivious routing algorithms for general undirected networks were introduced by Räcke [17], and this work has led to many subsequent improvements and applications. Comparatively little is known...
Fractal Merkle Tree Representation and Traversal (2003)
Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo
Abstract. We introduce a technique for traversal of Merkle trees, and propose an efficient algorithm that generates a sequence of leaves along with their associated authentication paths. For one...
The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly...
The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly...
A Survey of Algorithms for Integrating Wafer-Scale Systolic Arrays. (2002)
Leighton,Tom, Leiserson,Charles
VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble an...
Optimal Simulations of Tree Machines, (2002)
Bhatt,Sandeep, Chung,Fan, Leighton,Tom, Rosenberg,Arnold
Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead this reprint investigates simulations of tree machines;...
Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing. (2002)
Berger, Bonnie, Brady, Martin, Brown, Donna, Leighton, Tom
Channel routing plays a crucial role in the development of automated layout systems for integrated circuits. Most layout systems first place modules on a chip and then wire together terminals on...
A Survey of Problems and Results for Channel Routing (Extended Abstract), (2002)
Channel routing plays a central role in the development of automated layout systems for integrated circuits. Many layout systems first place modules on a chip or circuit board and then wire together...
Fan Chung, Ronald Graham, Tom Leighton
Suppose we are given some fixed (but unknown) subset X of a set Ω, and our object is to learn as much as possible about the elements of X by asking binary questions. Specifically, each question is...
Fan Chung, Ronald Graham, Tom Leighton
Suppose we are given some fixed (but unknown) subset X of a set\Omega\Gamma and our object is to learn as much as possible about the elements of X by asking binary questions. Specifically, each...
Universal-Stability Results and Performance Bounds for Greedy Contention-Resolution Protocols (2001)
Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Tom Leighton, Ziyong Liu, Jon Kleinberg, ...
In this paper, we analyze the behavior of packet-switched communication networks in which packets arrive dynamically at the nodes and are routed in discrete time steps across the edges. We This work...
Resource discovery in distributed networks (1999)
Mor Harchol-balter, Tom Leighton, Daniel Lewin
In large distributed networks of computers, it is often the case that a subset of machines wants to cooperate to perform a task. Before they can do so, these machines need to learn of the existence...
Resource Discovery in Distributed Networks (1999)
Mor Harchol-balter, Tom Leighton, Daniel Lewin
In large distributed networks of computers, it is often the case that a subset of machines wants to cooperate to perform a task. Before they can do so, these machines need to learn of the existence...
Fast algorithms for finding O(congestion + dilation) packet routing schedules (1999)
Tom Leighton, Bruce Maggs, Andréa W. Richa
In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to...
Space-Efficient Queue Management Using Fixed-Connection Networks, (1998)
On of the main difficulties in designing algorithms for large scale parallel machines is making sure that the capacities of the local memories are not exceeded. This paper presents a general scheme...
Universal Packet Routing Algorithms. (1998)
Leighton, Tom, Maggs, Bruce, Rao, Satish
This paper examines the packet routing problem in a network independent context. The goal is to devise a strategy for routing that works well for a wide variety of networks. To achieve this goal, the...
Dynamic Embedding of Trees in Hypercubes with Constant Dilation and Load. (1998)
Leighton, Tom, Newman, Mark, Schwabe, Eric
Parallel computations often yield computation structures which are trees; the shape of such a tree evolves over time as the computation progresses. However, parallel computers are usually designed as...
Fast Computation Using Faulty Hypercubes, (1998)
Hastad, Johan, Leighton, Tom, Newman, Mark
Consider the computational power of a hypercube containing a potentially large number of randomly located faulty components. Describe a randomized algorithm which embeds an N-node hypercube in an...
Nearly Optimal Algorithms and Bounds for Multilayer Channel Routing, (1998)
Berger, Bonnie, Brady, Martin, Brown, Donna, Leighton, Tom
Channel routing plays an important role in the development of automated layout systems for integrated circuits. Many layout systems first place modules on a chip and then wire together terminals on...
Bui, Thang, Heigham, Christopher, Jones, Curt, Leighton, Tom
In this paper, we compare the performance of two popular graph bisection algorithms. We also present an empirical study of a new heuristic, first proposed in Bui, Chaudhuri, Leighton, Sipser that...
Work-Preserving Emulations of Fixed-Connection Networks, (1998)
Koch, Richard, Leighton, Tom, Maggs, Bruce, Rao, Satish, Rosenberg, Arnold
In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. Although many isolated emulation results have been proved for specific networks in...
A 2d - 1 Lower Bound 2-Layer Knock-Knee Channel Routing. (1998)
In this paper, we describe a 2-point net channel routing problem with density d that requires channel width 2d - 1 in the 2-layer knock-knee channel routing model. This means that the (2d - 1)-track...
Work-Preserving Emulations of Fixed-Connection Networks, (1998)
Koch, Richard, Leighton, Tom, Maggs, Bruce, Rao, Satish, Rosenberg, Arnold
In this paper the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is O(TGNG/NH)...
VLSI Design, Parallel Computation and Distributed Computing. (1998)
Research efforts have centered in the areas of parallel and distributed computing, network architecture, combinatorial algorithms, and complexity theory. Significant progress has been made on the...
Fast Approximation Algorithms for Multicommodity Flow Problems, (1998)
Leighton, Tom, Makedon, Fillia, Plotkin, Serge, Stein, Clifford, Tardos, Eva, Tragoudas, Spyros
In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. Our algorithms are significantly faster than the best...
The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian (1998)
Guattery, Stephen, Leighton, Tom, Miller, Gary L.
We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical...
Hypercubic sorting networks (1998)
Abstract. This paper provides an analysis of a natural d-round tournamentover n = 2
General dynamic routing with per-packet delay guarantees of O(distance + 1/session rate (1997)
Matthew Andrews, Antonio Fernhndezt, Mor Harchol-balters, Tom Leighton, Lisa Zhangg
A central issue in the design of modern communi-cation networks is that of providing performance guar-antees. This issue is particularly important if the net-works support real-time trafic such as...
David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for...
The Path Resistance Method for bounding # 2 of a Laplacian (1997)
Stephen Guattery, Tom Leighton, Gary L. Miller
We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical...
General Dynamic Routing with Per-Packet Delay Guarantees of O( distance + 1 / session rate ) (1997)
Matthew Andrews, Antonio Fernández, Mor Harchol-balter, Tom Leighton, Lisa Zhang
A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as...
General Dynamic Routing with Per-Packet Delay Guarantees of O( distance + 1 / session rate ) (1997)
Matthew Andrews, Antonio Fernandez, Mor Harchol-balter, Tom Leighton, Lisa Zhang
A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as...
The Path Resistance Method for Bounding the Smallest Nontrivial Eigenvalue of a Laplacian (1997)
Stephen Guattery (icase, Stephen Guattery, Gary L. Miller, Tom Leighton, L. Miller
. We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical...
General Dynamic Routing with Per-Packet Delay Guarantees of (1997)
Distance Session, Matthew Andrews, Mor Harchol-balter, Tom Leighton, Lisa Zhang
A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic such as...
General dynamic routing with per-packet delay guarantees of O(distance + 1/session rate (1997)
Matthew Andrews, Antonio Fern Ández, Mor Harchol-balter, Tom Leighton, Lisa Zhang
Abstract. A central issue in the design of modern communication networks is that of providing performance guarantees. This issue is particularly important if the networks support real-time traffic...
David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy Abstract
We describe a family of caching protocols for distrib-uted networks that can be used to decrease or eliminate the occurrence of hot spots in the network. Our protocols are particularly designed for...
Universal Stability Results for Greedy Contention-Resolution Protocols (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Jon Kleinberg, Tom Leighton, Zhiyong Liu
In this paper, we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic...
Baruch Awerbuch, Yossi Azar, Tom Leighton
In this paper, we formulate and provide optimal solutions for a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the...
Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules (1996)
Tom Leighton, Bruce Maggs, A.W. Richa, Andr'ea W. Richa
In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to...
Notes on Better Master Theorems for Divide-and-Conquer Recurrences (1996)
Techniques for solving divide-and-conquer recurrences are routinely taught to thousands of Computer Science students each year. The dominant approach to solving such recurrences is known as the...
Reconstructing a Three-Dimensional Model with Arbitrary Errors (1996)
Bonnie Berger, Jon Kleinberg, Tom Leighton
A number of current technologies allow for the determination of inter-atomic distance information in structures such as proteins and RNA. Thus, the reconstruction of a three-dimensional set of points...
Baruch Awerbuch, Yossi Azar, Tom Leighton
In this paper, we formulate and provide optimal solutions for a broad class of problems in which a decision-maker is required to select from among numerous competing options. The goal of the...
Improved Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract) (1996)
Matthew Andrews, Tom Leighton, P. Takis Metaxas, Lisa Zhang
) Matthew Andrews Tom Leighton y P. Takis Metaxas z Lisa Zhang x Abstract In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and...
Automatic Methods for Hiding Latency in High Bandwidth Networks (Extended Abstract) (1996)
Matthew Andrews, Tom Leighton, P. Takis Metaxas, Lisa Zhang
In this paper we describe methods for mitigating the degradation in performance caused by high latencies in parallel and distributed networks. Our approach is similar in spirit to the...
Universal Stability Results for Greedy Contention-Resolution Protocols (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon Kleinberg, Tom Leighton, Zhiyong Liu
In this paper, we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic...
Universal Stability Results for Greedy Contention-Resolution Protocols (1996)
Matthew Andrews, Baruch Awerbuch, Antonio Fernández, Jon Kleinberg, Tom Leighton, Zhiyong Liu
In this paper, we analyze the behavior of communication networks in which packets are generated dynamically at the nodes and routed in discrete time steps across the edges. We focus on a basic...
Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules (1995)
In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to...
On Probabilistic Networks for Selection, Merging, and Sorting (1995)
Tom Leighton, Yuan Ma, Torsten Suel
We study comparator networks for selection, merging, and sorting that output the correct result with high probability given a random input permutation. We prove tight bounds, up to constant factors,...
Greedy Dynamic Routing on Arrays (1995)
We study the problem of dynamic routing on arrays. We prove that a large class of greedy algorithms perform very well on average. In the dynamic case, when the arrival rate of packets in an N \Theta...
Secure Spread Spectrum Watermarking for Multimedia (1995)
Ingemar J. Cox, Joe Kilian, Tom Leighton, Talal Shamoon
We describe a digital watermarking method for use in audio, image, video and multimedia data. We argue that a watermark must be placed in perceptually significant components of a signal if it is to...
Lower Bounds for Sorting Networks (1995)
Nabil Kahale, Tom Leighton, Yuan Ma, C. Greg Plaxton, Torsten Suel, Endre Szemerédi
We establish a lower bound of (1:12 \Gamma o(1)) n log n on the size of any n-input sorting network; this is the first lower bound that improves upon the trivial information-theoretic bound by more...
Circuit Switching: A Multicommodity Flow Based Approach. (1995)
In this paper, we consider the problem of routing virtual circuits in a network. In particular, given a set of request pairs in a network, we wish to route a path between each pair so that very few...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems...
Fast approximation algorithms for multicommodity flow problems (1994)
Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas
z
In this paper, we describe a very simple boundedqueuesize local-control algorithm for routing multicommodity flows in a dynamically-changing distributed network. The algorithm is based on the...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
In this paper, we consider the problems of admission control and virtual circuit routing in high performance computing and communication systems. The admission control and virtual circuit routing...
Doubly Logarithmic Communication Algorithms for Optical Communication Parallel Computers (1994)
Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, Satish Rao, Tom Leighton Mit
In this paper we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the Completely Connected Optical Communication...
Baruch Awerbuch, Rainer Gawlick, Tom Leighton, Yuval Rabani
This paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems...
Failsafe Key Escrow Systems (Extended Abstract) (1994)
This paper describes a method for escrowing cryptographic keys, which we call Failsafe Key Escrow (FKE). The method is sub-stantially more secure than alternatives such as the Fair Public Key...
\Fair " Public Key Cryptosystems (FPKCs) have recently been pro-posed as a method for providing secure escrowing of keys without rely-ing on special purpose hardware. In a fair public key...
The Statistical Adversary Allows Optimal Money-Making Trading Strategies (Extended Abstract) (1993)
Andrew Chou, Jeremy Cooperstock, Ran El-Yaniv, Michael Klugerman, Tom Leighton
Andrew Chou Jeremy Cooperstock y Ran El--Yaniv z Michael Klugerman x Tom Leighton -- November, 1993 Abstract The distributional approach and competitive analysis have traditionally been used for the...
A Simple Local-Control Approximation Algorithm for Multicommodity Flow (1993)
In this paper, we describe a very simple (1 + ")- approximation algorithm for the multicommodity flow problem. The algorithm runs in time that is polynomial in N (the number of nodes in the...
Fast Approximation Algorithms for Multicommodity Flow Problems (1993)
Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas
All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms [15] uses a fast matrix multiplication...
On the Fault Tolerance of Some Popular Bounded-Degree Networks (1992)
Tom Leighton, Bruce Maggs, R. Sitaraman
In this paper, we analyze the ability of several bounded-degree networks that are commonly used for parallel computation to tolerate faults. Among other things, we show that an N-node butterfly...
Highly fault-tolerant sorting circuits (1991)
Tom Leighton, Yuan Ma, C. Greg Plaxton
In this paper, we consider the problem of constructing a sorting circuit that will work well even if a constant fraction of its comparators fail at random. We consider two types of comparator...
Tight Bounds For On-Line Tree Embeddings (1991)
Sandeep Bhatt, David Greenberg, Tom Leighton, Pangfeng Liu
. Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network....
Fast Approximation Algorithms for Multicommodity Flow Problems (1991)
Tom Leighton, Fillia Makedon, Serge Plotkin, Clifford Stein, Eva Tardos, Spyros Tragoudas
All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms [15] uses a fast matrix multiplication...
Wafer-Scale Integration of Systolic Arrays (1985)
Abstract-VLSI technologists are fast developing wafer-scale integration. Rather than partitioning a silicon wafer into chips as is usually done, the idea behind wafer-scale integration is to assemble...
Planar embedding of planar graphs (1984)
Danny Dolev, Tom Leighton, Howard Trickey
Planar embedding with minimal area of graphs on an integer grid is an interesting problem in VLSI theory. Valiant [12] gave an algorithm to construct a planar embedding for trees in linear area, he...
Improving Performance on the Internet (0000)
When it comes to achieving performance, reliability, and scalability for commercial-grade Web applications, people see that the limiting bottleneck is the middle mile, or the time data spends...
Improving Performance on the Internet
When it comes to achieving performance, reliability, and scalability for commercial-grade Web applications, people see that the limiting bottleneck is the middle mile, or the time data spends...