Lujun Jia, Rajmohan Rajaraman, Torsten Suel
Abstract The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed...
Efficient Query Subscription Processing for Prospective Search Engines (2008)
Utku Irmak, Svilen Mihaylov, Torsten Suel
Current web search engines are retrospective in that they limit users to searches against already existing pages. Prospective search engines, on the other hand, allow users to upload queries that...
New Protocols for Remote File Synchronization Based on Erasure Codes£ (2008)
Utku Irmak, Svilen Mihaylov, Torsten Suel
Given two versions of a file, a current version located on one machine and an outdated version known only to another machine, the remote file synchronization problem is how to update the outdated...
16:25–16:50 WebRelievo: A System for Browsing and Analyzing the (2008)
Mark Levene, Ra Poulovassilis, Judit Bar-ilan, Mark Levene, Mazlita Mat-hassan, Yen-yu Chen, ...
14:50–15:15 Modeling Semantic Web Services with OPM/S A Human and Machine-Interpretable Language
Abstract Towards Efficiemlcy and Portability: Programming with the BSP Model (2008)
Mark Gouclreau, Kevin Lang, Satish Rao, Torsten Suel
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a model for general-purpose parallel computa-tion. The objective of the model is to allow the design of parallel programs that can...
Compressing File Collections with a TSP-Based Approach (2008)
Dimitre Trendafilov, Nasir Memon, Torsten Suel, Dimitre Trendafilov, Nasir Memon, Torsten Suel
Delta compression techniques solve the problem of encoding a given target file with respect to one or more reference files. Recent work in [15, 12, 7] has demonstrated the benefits of using such...
Design and Implementation of a High-PerformanceDistributed Web Crawler \Lambda (2008)
Vladislav Shkapenyuk, Torsten Suel
Abstract Broad web search engines as well as many more special-ized search tools rely on web crawlers to acquire large collections of pages for indexing and analysis. Such a webcrawler may interact...
ABSTRACT Local Methods for Estimating PageRank Values (2008)
Yen-yu Chen, Qingqing Gan, Torsten Suel
The Google search engine uses a method called PageRank, together with term-based and other ranking techniques, to order search results returned to the user. PageRank uses link analysis to assign a...
Efficient Query Subscription Processing for Prospective Search Engines (2008)
Utku Irmak, Svilen Mihaylov, Torsten Suel
Current web search engines are retrospective in that they limit users to searches against already existing pages. Prospective search engines, on the other hand, allow users to upload queries that...
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...
A Super-Logarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks (2007)
Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input shuffleunshuffle...
A Proposal for the BSP Worldwide Standard Library (preliminary version) (2007)
Mark Goudreau, Kevin Lang, Bill Mccoll, Satish B. Rao, Dan C. Stefanescu, ...
This memory area is reguarded as unregistered. 6. The explicit registration mechanism removes possible implicit assumptions about the compilation of static data as used by the Cray SHMEM and Oxford...
Services General Terms Algorithms, Performance (2007)
Yen-yu Chen, Qingqing Gan, Torsten Suel
ranking Over the last few years, most major search engines have integrated link-based ranking techniques in order to provide more accurate search results. One widely known approach is the Pagerank...
Torsten Suel, Chandan Mathur, Jo-wen Wu, Jiangong Zhang, Alex Delis, Mehdi Kharrazi, ...
We consider the problem of building a P2P-based search engine for massive document collections. We describe a prototype system called ODISSEA (Open DIStributed Search Engine Architecture) that is...
Lars Arge, Octavian Procopiuc, Torsten Suel
Abstract. Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process, or solve the problem by sorting, partitioning, or on-the-fly...
Lujun Jia, Rajmohan Rajaraman, Torsten Suel
The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network...
On Randomized and Deterministic Schemes for Routing and Sorting on Fixed-Connection Networks (2007)
Abstract. We give a high-level description of some fundamental randomized and deterministic techniques for routing and sorting on xedconnection networks such as meshes, hypercubes or point-to-point...
Server-Friendly Delta Compression for Efficient Web Access (2007)
A number of researchers have studied delta compression techniques for improving the efficiency of web page accesses over slow communication links. Most of these schemes exploit the fact that updated...
On the Scalability of an Image Transcoding Proxy Server (2007)
Anubhav Savant, Nasir Memon, Torsten Suel
Image transcoding proxies are used to improve Web browsing over low bandwidth networks by adapting content-rich web images to bandwidth-constrained clients. Such transcoding proxies dynamically...
A Super-Logarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks (2007)
Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input shuffleunshuffle...
Torsten Suel, Chandan Mathur, Jo-wen Wu, Jiangong Zhang, Alex Delis, Mehdi Kharrazi, ...
We consider the problem of building a P2P-based search engine for massive document collections. We describe a prototype system called ODISSEA (Open DIStributed Search Engine Architecture) that is...
On Randomized and Deterministic Schemes for Routing and Sorting on Fixed-Connection Networks (2007)
Abstract. We give a high-level description of some fundamental randomized and deterministic techniques for routing and sorting on fixedconnection networks such as meshes, hypercubes or point-to-point...
Approximate Maximum Weight Branchings (2005)
Amitabha Bagchi, Ankur Bhargava, Torsten Suel
We consider a special subgraph of a weighted directed graph: one comprising only the k heaviest edges incoming to each vertex. We show that the maximum weight branching in this subgraph closely...
Three-Level Caching for Efficient Query Processing in Large Web Search Engines (2005)
Large web search engines have to answer thousands of queries per second with interactive response times. Due to the sizes of the data sets involved, often in the range of multiple terabytes, a single...
Hierarchical Substring Caching for Efficient Content Distribution to Low-Bandwidth Clients (2005)
While overall bandwidth in the internet has grown rapidly over the last few years, and an increasing number of clients enjoy broadband connectivity, many others still access the internet over much...
Efficient Query Evaluation on Large Textual Collections in a Peer-to-Peer Environment (2005)
We study the problem of evaluating ranked (top-k) queries on textual collections ranging from multiple gigabytes to terabytes in size. We focus on the case of a global index organization in a highly...
Approximate Maximum Weight Branchings (2005)
Amitabha Bagchi, Ankur Bhargava, Torsten Suel
We consider a special subgraph of a weighted directed graph: one comprising only the k heaviest edges incoming to each vertex. We show that the maximum weight branching in this subgraph closely...
Optimal Peer Selection for P2P Downloading and Streaming (2005)
Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, Torsten Suel, David D. Yao
Abstract — In a P2P system, a client peer may select one or more server peers to download a specific file. In a P2P resource economy, the server peers charge the client for the downloading. A...
Improved single-round protocols for remote file synchronization (2005)
Utku Irmak, Svilen Mihaylov, Torsten Suel
Abstract — Given two versions of a file, a current version located on one machine and an outdated version known only to another machine, the remote file synchronization problem is how to update the...
Optimal Peer Selection for P2P Downloading and Streaming (2005)
Micah Adler, Rakesh Kumar, Keith Ross, Dan Rubenstein, Torsten Suel, David D. Yao
Abstract — In a P2P system, a client peer may select one or more server peers to download a specific file. In a P2P resource economy, the server peers charge the client for the downloading. A...
Design and implementation of a geographic search engine (2005)
Alexander Markowetz, Yen-yu Chen, Torsten Suel
In this paper, we describe the design and initial implementation of a geographic search engine prototype for Germany, based on a large crawl of the de domain. Geographic search engines provide a...
Local Methods for Estimating PageRank Values (2004)
Yen-yu Chen, Qingqing Gan, Torsten Suel
The Google search engine uses a method called PageRank, together with term-based and other ranking techniques, to order search results returned to the user. PageRank uses link analysis to assign a...
Improved File Synchronization Techniques for Maintaining (2004)
Large Replicated Collections, Torsten Suel, Patrick Noel, Dimitre Trendafilov
We study the problem of maintaining large replicated collections of files or documents in a distributed environment with limited bandwidth. This problem arises in a number of important applications,...
Odissea: A peer-to-peer architecture for scalable web search and information retrieval (2003)
Torsten Suel, Chandan Mathur, Jo-wen Wu, Jiangong Zhang, Alex Delis, Mehdi Kharrazi, ...
Most major search engines are currently based on cluster architectures, with large numbers of low-cost servers located at one or a few locations and connected by high-speed LANs [2]. Recently, there...
Inferring Tree Topologies Using Flow Tests (2003)
S. Muthukrishnan, Torsten Suel, Radek Vingralek
We consider the problem of discovering the structure of an unknown hierarchical network by means of measuring the maximum flow between the root and selected
Server-friendly delta compression for efficient web access (2003)
A number of researchers have studied delta compression techniques for improving the efficiency of web page accesses over slow communication links. Most of these schemes exploit the fact that updated...
ODISSEA: A Peer-to-Peer Architecture for Scalable Web Search and Information Retrieval (2003)
Torsten Suel, Chandan Mathur, Jo-Wen Wu, Jiangong Zhang, Alex Delis, Mehdi Kharrazi, ...
We consider the problem of building a P2P-based search engine for massive document collections. We describe a prototype system called ODISSEA (Open DIStributed Search Engine Architecture) that is...
ODISSEA: A Peer-to-Peer Architecture for Scalable Web Search and Information Retrieval (2003)
T. Suel, C. Mathur, J. Zhang, Alex Delis, M. Kharrazi, X. Long, ...
We consider the problem of building a P2P-based search engine for massive document collections. We describe a prototype system called ODISSEA (Open DIStributed Search Engine Architecture) that is...
Cluster-based delta compression of a collection of files (2002)
Zan Ouyang, Zan Ouyang, Nasir Memon, Nasir Memon, Torsten Suel, Torsten Suel, ...
Delta compression techniques are commonly used to succinctly represent an updated version of a file with respect to an earlier one. In this paper, we study the use of delta compression in a somewhat...
zdelta: An efficient delta compression tool (2002)
Dimitre Trendafilov, Dimitre Trendafilov, Nasir Memon, Nasir Memon, Torsten Suel, Torsten Suel
In this report we describe a tool for delta compression, i.e., the efficient encoding of a given data set in relation to another one. Its possible applications include archiving multiple versions of...
Design and implementation of a high-performance distributed web crawler (2002)
Vladislav Shkapenyuk, Torsten Suel
Broad web search engines as well as many more specialized search tools rely on web crawlers to acquire large collections of pages for indexing and analysis. Such a web crawler may interact with...
Cluster-based delta compression of a collection of files (2002)
Zan Ouyang, Nasir Memon, Torsten Suel, Dimitre Trendafilov
Delta compression techniques are commonly used to succinctly represent an updated version of a file with respect to an earlier one. In this paper, we study the use of delta compression in a somewhat...
Algorithms for delta compression and remote file synchronization (2002)
Delta compression and remote file synchronization techniques are concerned with efficient file transfer over a slow communication link in the case where the receiving party already has a similar file...
Design and implementation of a high-performance distributed web crawler (2002)
Vladislav Shkapenyuk, Vladislav Shkapenyuk, Torsten Suel, Torsten Suel
Broad web search engines as well as many more specialized search tools rely on web crawlers to acquire large collections of pages for indexing and analysis. Such a web crawler may interact with...
Cluster-based delta compression of a collection of files (2002)
Zan Ouyang, Zan Ouyang, Nasir Memon, Nasir Memon, Torsten Suel, Torsten Suel, ...
Delta compression techniques are commonly used to succinctly represent an updated version of a file with respect to an earlier one. In this paper, we study the use of delta compression in a somewhat...
I/o-efficient techniques for computing Pagerank (2002)
Yen-yu Chen, Yen-yu Chen, Qingqing Gan, Qingqing Gan, Torsten Suel, Torsten Suel
Over the last few years, most major search engines have integrated link-based ranking techniques in order to provide more accurate search results. One widely known approach is the Pagerank technique,...
Compressing the graph structure of the Web (2001)
A large amount of research has recently focused on the graph structure (or link structure) of the World Wide Web. This structure has proven to be extremely useful for improving the performance of...
Compressing the graph structure of the Web (2001)
A large amount of research has recently focused on the graph structure (or link structure) of the World Wide Web. This structure has proven to be extremely useful for improving the performance of...
Gavriel Yarmish, Gabriel Yarmish, Minor Financial Engineering, Richard Van Slyke, Alex Delis, Torsten Suel
by
A unified approach for indexed and non-indexed spatial joins (2000)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter
Abstract. Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process,or solve the problem by sorting, partitioning, or on-the-fly...
A Super-Logarithmic Lower Bound for Shuffle-Unshuffle Sorting Networks (2000)
Greg Plaxton Torsten, Torsten Suel
Shuffle-unshuffle sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input shuffleunshuffle...
A Unified Approach For Indexed and Non-Indexed Spatial Joins (2000)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Jeffrey Scott Vitter, Jan Vahrenhold, Torsten Suel
A large number of spatial join algorithms have been proposed over the last few years. Most of the algorithms can be broadly categorized into two approaches. The first approach assumes the existence...
A Unified Approach For Indexed and (2000)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process, or solve the problem by sorting, partitioning, or on-the-fly index...
A unified approach for indexed and non-indexed spatial joins (2000)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jan Vahrenhold, Jeffrey Scott Vitter
Abstract. Most spatial join algorithms either assume the existence of a spatial index structure that is traversed during the join process,or solve the problem by sorting, partitioning, or on-the-fly...
Portable and Efficient Parallel Computing Using the BSP Model (1999)
Mark Goudreau, Kevin Lang, Satish B. Rao, Torsten Suel, Thanasis Tsantilas
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically...
Compact Grid Layouts of Multi-Level Networks (1999)
S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel
We consider the problem of generating layouts of multilevel networks, in particular, switching, sorting, and interconnection networks, as compactly as possible on VLSI grids. Besides traditional...
Compact Grid Layouts of Some Multi-Level Networks (1999)
Muthukrishnan Michael, Michael S. Paterson, Torsten Suel
We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible, that is, with minimum area, on VLSI...
Compact Grid Layouts of Some Multi-Level Networks (1999)
S. Muthukrishnan, Michael S. Paterson, Suleyman Cenk Sahinalp, Torsten Suel
We consider the problem of generating layouts of multi-level networks, in particular, switching, sorting, and interconnection networks, as compactly as possible, that is, with minimum area, on VLSI...
Scalable Sweeping-Based Spatial Join (1998)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
In this paper, we consider the filter step of the spatial join problem, for the case where neither of the inputs are indexed. We present a new algorithm, Scalable Sweeping-Based Spatial Join (SSSJ),...
Second-Order Methods for Distributed Approximate Single- and Multicommodity Flow (1998)
S. Muthukrishnan, Torsten Suel
We study local-control algorithms for maximum flow and multicommodity flow problems in distributed networks. We propose a second-order method for accelerating the convergence of the...
Optimal Histograms with Quality Guarantees (1998)
H. V. Jagadish, Viswanath Poosala, Nick Koudas, Ken Sevcik, S. Muthukrishnan, Torsten Suel
Histograms are commonly used to capture attribute value distribution statistics for query optimizers. More recently, histograms have also been considered as a way to produce quick approximate answers...
Scalable Sweeping-Based Spatial Join (1998)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
In this paper, we consider the filter step of the spatial join problem, for the case where neither of the inputs are indexed. We present a new algorithm, Scalable Sweeping-Based Spatial Join (SSSJ),...
Scalable Sweeping-Based Spatial Join (1998)
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
In this paper, we examine the spatial join problem. In particular, we focus on the case when neither of the inputs is indexed. We present a new algorithm, Scalable Sweep-based Spatial Join (SSSJ),...
BSPlib: The BSP Programming Library (1998)
Bill Mccoll, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang, Satish B. Rao, ...
BSPlib is a small communications library for bulk synchronous parallel (BSP) programming which consists of only 20 basic operations. This paper presents the full definition of BSPlib in C, motivates...
Extend Ed, Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
) Lars Arge Octavian Procopiuc y Sridhar Ramaswamy z Torsten Suel x Jeffrey Scott Vitter -- Abstract We describe a powerful framework for designing efficient batch algorithms for certain large-scale...
BSPlib: The BSP Programming Library (1998)
Jonathan Hill, Bill Mccoll, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang, Satish B. Rao, ...
BSPlib is a small communications library for bulk synchronous parallel (BSP) programming which consists of only 20 basic operations. This paper presents the full definition of BSPlib in C, motivates...
Portable and Efficient Parallel Computing Using the BSP Model (1998)
Mark W. Goudreau, Kevin Lang, Satish B. Rao, Torsten Suel, Thanasis Tsantilas
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically...
Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter
We describe a powerful framework for designing efficient batch algorithms for certain large-scale dynamic problems that must be solved using external memory. The class of problems we consider, which...
Highly Portable and Efficient Implementations of Parallel Adaptive N-Body Methods (1997)
We describe the design of several portable and efficient parallel implementations of adaptive N-body methods, including the adaptive Fast Multipole Method, the adaptive version of Anderson's...
BSPlib - The BSP Programming Library (1997)
Bill Mccoll, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang, Satish B. Rao, ...
This memory area is regarded as unregistered. 6. While registration is designed for "full duplex" communication, a process can do half duplex communication by, appropriately, registering an...
Highly Portable and Efficient Implementations of Parallel Adaptive N-Body Methods (1997)
We describe the design of several portable and efficient parallel implementations of adaptive N-body methods, including the adaptive Fast Multipole Method, the adaptive version of Anderson's...
Http://www.bsp-Worldwide.org/ (1997)
May Ansi, Bill Mccoll, Dan C. Stefanescu, Mark W. Goudreau, Kevin Lang, ...
This memory area is regarded as unregistered. 6. While registration is designed for "full duplex" communication, a process can do half duplex communication by, appropriately, registering an...
Towards Efficiency and Portability: Programming with the BSP Model (1996)
Mark Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a model for general-purpose parallel computation. The objective of the model is to allow the design of parallel programs that can...
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,...
Beyond the Worst-Case Bisection Bound: Fast Sorting and Ranking on Meshes (1995)
Michael Kaufmann, Jop F. Sibeyn, Torsten Suel
Sorting is an important subroutine in many parallel algorithms and has been studied extensively on meshes and related networks. If every processor of an n \Theta n mesh is the source and destination...
Beyond the Worst-Case Bisection Bound: Fast Sorting and Ranking on Meshes (1995)
Michael Kaufmann, Jop F. Sibeyn, Torsten Suel
Sorting is an important subroutine in many parallel algorithms and has been studied extensively on meshes and related networks. If every processor of an n \Theta n mesh is the source and destination...
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...
A lower bound for sorting networks based on the shuffle permutation (1994)
We prove an \Omega\Gamma/1 2 n = lg lg n) lower bound for the depth of n-input sorting networks based on the shuffle permutation. The best previously known lower bound was the trivial \Omega\Gammaiv...
A super-logarithmic lower bound for hypercubic sorting networks (1994)
Hypercubic sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input hypercubic sorting networks...
Routing and sorting on meshes with row and column buses (1994)
We give improved deterministic algorithms for permutation routing and sorting on meshes with row and column buses. Among our results, we obtain a fairly simple algorithm for permutation routing on...
Derandomizing Algorithms for Routing and Sorting on Meshes (1994)
Michael Kaufmann, Jop F. Sibeyn, Torsten Suel
We describe a new technique that can be used to derandomize a number of randomized algorithms for routing and sorting on meshes. We demonstrate the power of this technique by deriving improved...
A lower bound for sorting networks based on the shuffle permutation (1994)
We prove an \Omega\Gamma/1 2 n = lg lg n) lower bound for the depth of n-input sorting networks based on the shuffle permutation. The best previously known lower bound was the trivial \Omega\Gammaiv...
Routing and Sorting on Fixed Topologies (1994)
Dissertation Committee, Torsten Suel, Torsten Suel, Torsten Suel, ...
v Chapter 1 Introduction 1 1.1 Model of Computation : : : : : : : : : : : : : : : : : : : : : : : : : : 2 1.2 Fixed-Connection Networks : : : : : : : : : : : : : : : : : : : : : : : 4 1.2.1...
A Lower Bound for Sorting Networks Based on the Shuffle Permutation (1994)
We prove an \Omega\Gamma/1 2 n= lg lg n) lower bound for the depth of sorting networks based on the shuffle permutation. This settles an open question posed by Knuth, up to a \Theta(lg lg n) factor....
A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks (1994)
Hypercubic sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input hypercubic sorting networks...
Derandomizing Algorithms for Routing and Sorting on Meshes (1994)
Michael Kaufmann, Jop F. Sibeyn, Torsten Suel
We describe a new technique that can be used to derandomize a number of randomized algorithms for routing and sorting on meshes. We demonstrate the power of this technique by deriving improved...
Optimal Deterministic Routing and Sorting on Mesh-Connected Arrays of Procesors (1993)
the priorities of the elements are determined by the total Manhattan distances to the destination blocks. We identify every processor in the lower right quadrant by a pair of coordinates (x; y),...
Graph Augmentation And Related Problems: Theory And Practice (1993)
Tsan-Sheng Hsu, Torsten Suel, Roberto Tamassia
vi Table of Contents viii Chapter 1 Introduction 1 1.1 Background : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1 1.2 Summary of Thesis Results : : : : : : : : : : : : : : : : : : : : 5...
Improved lower bounds for Shellsort (1992)
We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an \Omega\Gamma n lg 2 n=(lg lg n) 2) lower bound for the size of Shellsort sorting...
Improved lower bounds for Shellsort (1992)
C. Greg Plaxton, Bjorn Poonen, Torsten Suel
We give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In...
Improved lower bounds for Shellsort (1992)
We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an \Omega\Gamma n lg 2 n=(lg lg n) 2) lower bound for the size of Shellsort sorting...
Improved Lower Bounds for Shellsort (1992)
C. Greg Plaxton, Bjorn Poonen, Torsten Suel
We give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In...