Arrow Research search

Author name cluster

Greg N. Frederickson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

FOCS Conference 1991 Conference Paper

Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees

  • Greg N. Frederickson

Ambivalent data structures are presented for several problems on undirected graphs. They are used in finding the k smallest spanning trees of a weighted undirected graph in O(m log beta (m, n)+min(k/sup 3/2/, km/sup 1/2/)) time, where m is the number of edges and n the number of vertices in the graph. The techniques are extended to find the k smallest spanning trees in an embedded planar graph in O(n+k(log n)/sup 3/) time. Ambivalent data structures are also used to maintain dynamically 2-edge-connectivity information. Edges and vertices can be inserted or deleted in O(m/sup 1/2/) time, and a query as to whether two vertices are in the same 2-edge-connected component can be answered in O(log n) time, where m and n are understood to be the current number of edges and vertices, respectively. Again, the techniques are extended to maintain an embedded planar graph so that edges and vertices can be inserted or deleted in O((log n)/sup 3/) time, and a query answered in O(log n) time. >

Details

FOCS Conference 1989 Conference Paper

Ensemble Motion Planning in Trees

  • Greg N. Frederickson
  • D. J. Guan

The problem of transporting a set of objects between the vertices of a tree by a unit capacity vehicle that travels along the edges of the tree is considered. For the case in which any object can be dropped at intermediate vertices along its route and picked up later, the authors present algorithms for finding a minimum cost transportation that run in O(k+qn) time and in O(k+n log n) time, where n is the number of vertices in the tree, k is the number of objects to be moved, and q<or=min(k, n) is the number of nontrivial connected components in a related directed graph. In the case in which each object must be carried directly from its initial vertex to its destination, the problem is NP-hard. The authors present approximation algorithms that run in O(k+n) time with a performance ratio of 3/2 and in O(k+n log beta (n, q)) time with performance ratio of 5/4.

Details

FOCS Conference 1989 Conference Paper

Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version)

  • Greg N. Frederickson

An algorithm for generating a succinct encoding of all-pairs shortest path information in an n-vertex directed planar G with O(n) edges is presented. The edges have real-valued costs, but the graph contains no negative cycles. The time complexity is given in terms of a topological embedding measure defined in the paper. The algorithm uses a decomposition of the graph into outerplanar subgraphs satisfying certain separator properties, and a linear-time algorithm is presented to find this decomposition. >

Details

FOCS Conference 1986 Conference Paper

Separator-Based Strategies for Efficient Message Routing (Preliminary Version)

  • Greg N. Frederickson
  • Ravi Janardan

Message routing strategies are given for networks with certain separator properties. These strategies use considerably less space than complete routing tables, keep node names to O(log n) bits, and still route along near-shortest paths. For any network with separators of size at most a small constant c, a total of O(n log n) items of routing information is stored, and any message is routed along a path of length at most (2/α) + 1 times the length of an optimal path, where α ≫ 1 is the positive root of the equation α⌈(c+1)/2⌉ - α - 2 = 0. For planar networks, O(n1+ε) items are stored, for any constant ε, 0 ≪ ε ≪ 1/3, and the length of any message path is at most 7 times that of an optimal path.

Details

FOCS Conference 1983 Conference Paper

Shortest Path Problems in Planar Graphs (Preliminary Version)

  • Greg N. Frederickson

Graph decomposition and data structures techniques are presented that make possible faster algorithms for shortest paths in planar graphs. Improved algorithms are presented for the single source problem, the all pairs problem, and the problem of finding a minimum cut in an undirected graph.

Details

FOCS Conference 1981 Conference Paper

Implicit Data Structures for the Weighted Dictionary Problem (preliminary version)

  • Greg N. Frederickson

Several new data structures are presented for dictionaries containing elements with different weights (access probabilities). The structures use just one location in addition to those required for the values of the elements, and support access times that are within a constant multiplicative factor of optimal, in terms of the rank of the weight of the desired element. Self-organizing heuristics are analyzed, in terms of both weights and "near-ranks" of weights. The benefits of additional space are investigated within the context of self-organization and unsuccessful search.

Details

FOCS Conference 1980 Conference Paper

Implicit Data Structures with Fast Update (Preliminary Report)

  • Greg N. Frederickson

Several new data structures for dictionaries are presented that use just one location in addition to those required for key values. The structures are generalizations of a rotated sorted list, with the best realizing a search time of 0(log n) and insert and delete times of 0(n√2/log n(log n)3/2). Similar structures are presented for a dictionary with records containing k≫1 keys, under the operations of search, partial match, insert and delete.

Details

FOCS Conference 1976 Conference Paper

Approximation Algorithms for some Routing Problems

  • Greg N. Frederickson
  • Matthew S. Hecht
  • Chul E. Kim

Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling Salesman problem, the Chinese Postman problem, and the Stacker-Crane problem, for which a minimax solution is sought. This heuristic has a bound of e + 1 - 1/k, where e is the bound for the corresponding 1-person algorithm.

Details