Testudo: Heavyweight Security Analysis via Statistical Sampling (2009)
Joseph L. Greathouse, Ilya Wagner, David A. Ramos, Gautam Bhatnagar, Todd Austin, Valeria Bertacco, ...
Heavyweight security analysis systems, such as taint analysis and dynamic type checking, are powerful technologies used to detect security vulnerabilities and software bugs. Traditional software...
Abstract New Constructions of (α, β)-Spanners and Purely Additive Spanners ∗ (2009)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An (α, β)-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u, v: δH(u, v) ≤ αδG(u, v) + β, where δG is the...
We consider the problem of preprocessing an edgeweighted tree Ì in order to quickly answer queries of the following type: does a given edge � belong in the minimum spanning tree of Ì...
The complexity of implicit and space-efficient priority queues (2008)
Christian W. Mortensen, Seth Pettie
Abstract. In this paper we study the time-space complexity of implicit priority queues supporting the decreasekey operation. Our first result is that by using one extra word of storage it is possible...
New Constructions of ¡ β ¢ α-Spanners and Purely Spanners£ Additive (2008)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An ¦ α § β ¨-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u § v: δH ¦ u § v¨� © αδG ¦ u § v¨� �...
Randomized Minimum Spanning Tree Algorithms Using Exponentially Fewer Random Bits (2008)
For many fundamental problems there exist randomized algorithms that are asymptotically optimal and are superior to the best known deterministic algorithm. Among these are the minimum spanning tree...
Additive Spanners and (α, β)-Spanners ∗ (2008)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a...
Sources of Superlinearity in Davenport-Schinzel Sequences (2008)
A generalized Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed forbidden subsequence. One of the fundamental problems in this area is...
An Inverse-Ackermann Style Lower Bound for Online Minimum Spanning Tree Verification (2008)
1 Introduction The minimum spanning tree (MST) problem has seen a flurry of activity lately, driven largely by the success of a new approach to the problem. The recent MST algorithms [20, 8, 29, 28],...
Low Distortion Spanners (2008)
Abstract. A spanner of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say H ⊆ G is an...
Sources of Superlinearity in Davenport-Schinzel Sequences (2008)
A {em generalized} Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed {em forbidden subsequence}. One of the fundamental problems in this...
Seth Pettie, Vijaya Ramachandran
We present a new algorithm for computing undirected shortest paths in the fundamental comparisonaddition model. Due to the generality of the model, our algorithm works on real-weighted undirected...
An inverse-Ackermann type lower bound for online minimum spanning tree verification (2007)
Given a spanning tree T of some graph G, the problem of minimum spanning tree veri cation is to decide whether T = MST (G). A celebrated result of Komlos shows that this problem can be solved in...
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specically, we present a deterministic algorithm to nd a minimum spanning...
Experimental Evaluation of a New Shortest Path Algorithm (2007)
Extended Abstract, Seth Pettie, Vijaya Ramach, Srinath Sridhar
Abstract. We evaluate the practical eciency of a new shortest path algorithm for undirected graphs which was developed by the rst two authors. This algorithm works on the fundamental...
Computing Undirected Shortest Paths with Comparisons and Additions (2007)
We study undirected shortest paths problems in a natural model of computation, namely one which gives us two numerical operations: comparisons and additions. This is the model assumed by such...
A Simpler Linear Time 2/3 − ε Approximation for Maximum Weight Matching (2007)
Seth Pettie, Peter Sanders, Peter S
We present two approximation algorithms for the maximum weight matching problem that run in time O m log . We give a simple and practical randomized algorithm and a somewhat more complicated...
Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture (2007)
We introduce a new technique to bound the asymptotic performance of splay trees. The basic idea is to transcribe, in an indirect fashion, the rotations performed by the splay tree as a...
Sources of Superlinearity in Davenport-Schinzel Sequences (2007)
A generalized Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed forbidden subsequence. One of the fundamental problems in this area is...
Splay trees, Davenport-Schinzel sequences, and the deque conjecture (2007)
We introduce a new technique to bound the asymptotic performance of splay trees. The basic idea is to transcribe, in an indirect fashion, the rotations performed by the splay tree as a...
Towards a Final Analysis of Pairing Heaps (2006)
Fredman, Sedgewick, Sleator, and Tarjan proposed the {em pairing heap} as a self-adjusting, streamlined version of the Fibonacci heap. It provably supports all priority queue operations in...
New constructions of (α, β)-spanners and purely additive spanners (2005)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An α�β-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u�v: δH u�v�αδG u�v β, where δG is the distance...
The complexity of implicit and space-efficient priority queues (2005)
Mortensen, Christian W, Pettie, Seth, Dehne, Frank, López-Ortiz, Alejandro, Sack, Jörg-Rüdiger
New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners (2005)
Baswana, Surender, Kavitha, Telikepalli, Mehlhorn, Kurt, Pettie, Seth
A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs (2004)
We present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. It runs in O(mn+n time, improving on the long-standing bound of...
On the shortest path and minimum spanning tree problems (2003)
Thesis (Ph. D.)--University of Texas at Austin, 2003.
On the shortest path and minimum spanning tree problems [electronic resource] (2003)
The shortest path and minimum spanning tree problems are two of the classic textbook problems in combinatorial optimization. They are simple to describe and admit simple polynomial-time algorithms....
A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs (2003)
We present a new all-pairs shortest path algorithm that works with real-weighted graphs in the traditional comparison-addition model. It runs in O(mn+n time, improving on the long-standing bound of...
Computing Shortest Paths with Comparisons and Additions (2002)
Seth Pettie, Vijaya Ramachandran
We present an undirected all-pairs shortest paths (APSP) algorithm which runs on a pointer machine in time O(mnot(m, n)) while making O(ran log a(m, n)) compar-isons and additions, where m and n are...
The dynamic vertex minimum problem (DVMP) is to maintain the minimum cost edge in a graph that is subject to vertex additions and deletions. DVMP abstracts the clustering operation that is used in...
A faster all-pairs shortest path algorithm for real-weighted sparse graphs (2002)
We present a faster all-pairs shortest paths algorithm for arbitrary real-weighted directed graphs. The algorithm works in the fundamental comparison-addition model and runs in O(mn + n 2 log log n)...
Abstract. The dynamic vertex minimum problem (DVMP) is to maintain the minimum cost edge in a graph that is subject to vertex additions and deletions. DVMP abstracts the clustering operation that is...
An Inverse-Ackermann Style Lower Bound for MST Verification Queries (2002)
We consider the problem of preprocessing an edge-weighted tree T in order to quickly answer queries of the following type: does a given edge e belong in the minimum spanning tree of T[feg? It is...
A faster all-pairs shortest path algorithm for real-weighted sparse graphs (2002)
Abstract. We present a faster all-pairs shortest paths algorithm for arbitrary real-weighted directed graphs. The algorithm works in the fundamental comparison-addition model and runs in O(mn+n 2 log...
The dynamic vertex minimum problem (DVMP) is to maintain the minimum cost edge in a graph that is subject to vertex additions and deletions. DVMP abstracts the clustering operation that is used in...
On the comparison-addition complexity of all-pairs shortest paths (2002)
We present an all-pairs shortest path algorithm for arbitrary graphs that performs O(mn log (m; n)) comparison and addition operations, where m and n are the number of edges and vertices, resp., and...
On the comparison-addition complexity of all-pairs shortest paths (2002)
Abstract. We present an all-pairs shortest path algorithm for arbitrary graphs that performs O(mn log ) comparison and addition operations, where m and n are the number of edges and vertices, resp.,...
An inverse-Ackermann style lower bound for the online minimum spanning tree veri problem (2002)
We consider the problem of preprocessing an edgeweighted tree T in order to quickly answer queries of the following type: does a given edge e belong in the minimum spanning tree of T [ feg? Whereas...
There are several fundamental problems whose deterministic complexity remains unresolved, but for which there exist randomized algorithms whose complexity is equal to known lower bounds. Among such...
Experimental evaluation of a new shortest path algorithm (2002)
Seth Pettie, Vijaya Ramach, Srinath Sridhar
We evaluate the practical eciency of a new shortest path algorithm for undirected graphs which was developed by the rst two authors. This algorithm works on the fundamental comparison-addition model....
Seth Pettie, Vijaya Ramachandran
There are several fundamental problems for which there are optimal randomized algorithms, but whose deterministic complexity remains unresolved. Among such problems are the minimum spanning tree...
Experimental evaluation of a new shortest path algorithm (2002)
Seth Pettie, Vijaya Ramach, Srinath Sridhar
Abstract. We evaluate the practical efficiency of a new shortest path algorithm for undirected graphs which was developed by the first two authors. This algorithm works on the fundamental...
An optimal minimum spanning tree algorithm (2000)
Seth Pettie, Vijaya Ramachandran
Abstract. We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a...
An optimal minimum spanning tree algorithm (2000)
We present a deterministic algorithm to find a minimum spanning forest of an edge-weighted undirected graph. On a graph with n vertices and m edges, the algorithm runs in time O(T
An optimal minimum spanning tree algorithm (2000)
Abstract. We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a...
An Optimal Minimum Spanning Tree Algorithm (2000)
Seth Pettie, Vijaya Ramachandran, Are T
We establish that the algorithmic complexity of the minimum spanning tree problem is equal to its decision-tree complexity. Specifically, we present a deterministic algorithm to find a minimum...
A randomized time-work optimal parallel algorithm for finding a minimum spanning forest (1999)
Seth Pettie, Vijaya Ramachandran
Abstract. We present a randomized algorithm to find a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an...
A randomized time-work optimal parallel algorithm for finding a minimum spanning forest (1999)
Seth Pettie, Vijaya Ramachandran
Abstract. We present a randomized algorithm to find a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an...
A randomized time-work optimal parallel algorithm for finding a minimum spanning forest (1999)
We present a randomized algorithm to find a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an EREW PRAM. This...
An Optimal Minimum Spanning Tree Algorithm (1999)
Seth Pettie And, Seth Pettie, Vijaya Ramach, Are T
We present a deterministic algorithm to find a minimum spanning forest of an edge-weighted undirected graph. On a graph with n vertices and m edges, the algorithm runs in time O(T (m; n)) where T is...
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest (1999)
Seth Pettie And, Seth Pettie, Vijaya Ramach
We present a randomized algorithm to find a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an EREW PRAM. This...
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest (1999)
Seth Pettie, Vijaya Ramachandran
. We present a randomized parallel algorithm to find a minimum spanning forest (MSF) in a weighted, undirected graph. On an EREW PRAM our algorithm runs in logarithmic time and linear work w.h.p....
Finding Minimum Spanning Trees in O(m α(m,n)) Time (1999)
We describe a deterministic minimum spanning tree algorithm running in time O(m ff(m; n)), where ff is a natural inverse of Ackermann's function and m and n are the number of edges and vertices,...
A randomized time-work optimal parallel algorithm for finding a minimum spanning forest (1999)
We present a randomized algorithm to nd a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an EREW PRAM. This...
A shortest path algorithm for real-weighted undirected graphs (1985)
Seth Pettie, Vijaya Ramachandran
Abstract. We present a new scheme for computing shortest paths on real-weighted undirected graphs in the fundamental comparison-addition model. In an efficient preprocessing phase our algorithm...