Greg N. Frederickson

Publication Activity (10 Years)

Years Active: 1976-2017
Publications (10 Years): 1

Top Topics

Precedence Constraints

Approximation Algorithms

Top Venues

Publications

Greg N. Frederickson, Samson Zhou
Optimal Parametric Search for Path and Tree Partitioning. CoRR (2017)
Greg N. Frederickson, Barry Wittman
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems. Algorithmica 62 (3-4) (2012)
Ethan Blanton, Sonia Fahmy, Greg N. Frederickson, Sriharsha Gangam
On the Cost of Network Inference Mechanisms. IEEE Trans. Parallel Distributed Syst. 22 (4) (2011)
Greg N. Frederickson, Barry Wittman
Speedup in the Traveling Repairman Problem with Constrained Time Windows CoRR (2011)
Greg N. Frederickson, Barry Wittman
Two Multivehicle Routing Problems with Unit-Time Windows CoRR (2011)
Greg N. Frederickson, Barry Wittman
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems CoRR (2009)
Ethan Blanton, Sonia Fahmy, Greg N. Frederickson
On the Utility of Inference Mechanisms. ICDCS (2009)
Greg N. Frederickson, Barry Wittman
Speedup in the Traveling Repairman Problem with Unit Time Windows CoRR (2009)
Mikhail J. Atallah, Greg N. Frederickson, Ashish Kundu
A tree-covering problem arising in integrity of tree-structured data. Inf. Process. Lett. 109 (1) (2008)
Greg N. Frederickson, Barry Wittman
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows. APPROX-RANDOM (2007)
Greg N. Frederickson
Unexpected Twists in Geometric Dissections. Graphs Comb. 23 (Supplement-1) (2007)
Greg N. Frederickson, Roberto Solis-Oba
Efficient algorithms for robustness in resource allocation and scheduling problems. Theor. Comput. Sci. 352 (1-3) (2006)
Erik D. Demaine, Martin L. Demaine, David Eppstein, Greg N. Frederickson, Erich Friedman
Hinged dissection of polyominoes and polyforms. Comput. Geom. 31 (3) (2005)
Robert A. Hearn, Erik D. Demaine, Greg N. Frederickson
Hinged Dissection of Polygons is Hard. CCCG (2003)
Greg N. Frederickson
Piano-Hinged Dissections: Now Let's Fold! JCDCG (2002)
Greg N. Frederickson
Geometric Dissections that Swing and Twist. JCDCG (2000)
Greg N. Frederickson, Roberto Solis-Oba
Increasing the Weight of Minimum Spanning Trees. J. Algorithms 33 (2) (1999)
Erik D. Demaine, Martin L. Demaine, David Eppstein, Greg N. Frederickson, Erich Friedman
Hinged Dissection of Polyominoes and Polyforms CoRR (1999)
Greg N. Frederickson
-Terminal Graphs. Algorithmica 22 (3) (1998)
Greg N. Frederickson, Roberto Solis-Oba
Algorithms for Measuring Perturbability in Matroid Optimization. Comb. 18 (4) (1998)
Greg N. Frederickson, Roberto Solis-Oba
Efficient Algorithms for Robustness in Matroid Optimization. SODA (1997)
Greg N. Frederickson
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees. SIAM J. Comput. 26 (2) (1997)
Anne Condon, Faith E. Fich, Greg N. Frederickson, Andrew V. Goldberg, David S. Johnson, Michael C. Loui, Steven Mahaney, Prabhakar Raghavan, John E. Savage, Alan L. Selman, David B. Shmoys
Strategic directions in research in theory of computing. SIGACT News 28 (3) (1997)
Greg N. Frederickson
A Data Structure for Dynamically Maintaining Rooted Trees. J. Algorithms 24 (1) (1997)
Greg N. Frederickson
Searching Among Intervals and Compact Routing Tables. Algorithmica 15 (5) (1996)
Greg N. Frederickson, Roberto Solis-Oba
Increasing the Weight of Minimum Spanning Trees. SODA (1996)
Greg N. Frederickson
Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems. J. Algorithms 19 (1) (1995)
Greg N. Frederickson, Susan H. Rodger
An NC Algorithm for Scheduling Unit-Time Jobs With Arbitrary Release Times and Deadlines. SIAM J. Comput. 23 (1) (1994)
Greg N. Frederickson
An Optimal Algorithm for Selection in a Min-Heap Inf. Comput. 104 (2) (1993)
Greg N. Frederickson
Searching among Intervals and Compact Routing Tables. ICALP (1993)
Greg N. Frederickson
A Data Structure for Dynamically Maintaining Rooted Trees. SODA (1993)
Greg N. Frederickson, Susanne E. Hambrusch, Hung-Yi Tu
Shortest Path Computations in Source-Deplanarized Graphs. Inf. Process. Lett. 47 (2) (1993)
Greg N. Frederickson, D. J. Guan
Nonpreemptive Ensemble Motion Planning on a Tree. J. Algorithms 15 (1) (1993)
Greg N. Frederickson
A Note on the Complexity of a Simple Transportation Problem. SIAM J. Comput. 22 (1) (1993)
Greg N. Frederickson, D. J. Guan
Preemptive Ensemble Motion Planning on a Tree. SIAM J. Comput. 21 (6) (1992)
Greg N. Frederickson
Editor's Foreword Special Issue on Graph Algorithms. Algorithmica 7 (5&6) (1992)
Greg N. Frederickson
Planar Graph Decomposition and All Pairs Shortest Paths. J. ACM 38 (1) (1991)
Greg N. Frederickson
Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees FOCS (1991)
Greg N. Frederickson
Parametric Search and Locating Supply Centers in Trees. WADS (1991)
Greg N. Frederickson
Optimal Algorithms for Tree Partitioning. SODA (1991)
Malcolm C. Fields, Greg N. Frederickson
A Faster Algorithm for the Maximum Weighted Tardiness Problem. Inf. Process. Lett. 36 (1) (1990)
Greg N. Frederickson
The Information Theory Bound Is Tight for Selection in a Heap STOC (1990)
Greg N. Frederickson, Ravi Janardan
Space-Efficient Message Routing in c-Decomposable Networks. SIAM J. Comput. 19 (1) (1990)
Greg N. Frederickson
A Distributed Shortest Path Algorithm for a Planar Network Inf. Comput. 86 (2) (1990)
Greg N. Frederickson, Donald B. Johnson
Erratum: Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 19 (1) (1990)
Greg N. Frederickson, Susan H. Rodger
A New Approach to the Dynamic Maintaince of Maximal Points in a Plane. Discret. Comput. Geom. 5 (1990)
Greg N. Frederickson, Ravi Janardan
Efficient Message Routing in Planar Networks. SIAM J. Comput. 18 (4) (1989)
Greg N. Frederickson, D. J. Guan
Ensemble Motion Planning in Trees FOCS (1989)
Greg N. Frederickson
Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version) FOCS (1989)
Greg N. Frederickson, Mandayam A. Srinivas
Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems. SIAM J. Comput. 18 (1) (1989)
Mikhail J. Atallah, Greg N. Frederickson, S. Rao Kosaraju
Sorting with Efficient Use of Special-Purpose Sorters. Inf. Process. Lett. 27 (1) (1988)
Greg N. Frederickson, Ravi Janardan
Space-Efficient and Fault-Tolerant Message Routing in Outerplanar Networks. IEEE Trans. Computers 37 (12) (1988)
Greg N. Frederickson, Ravi Janardan
Designing Networks with Compact Routing Tables. Algorithmica 3 (1988)
Greg N. Frederickson
Distributed Algorithms for Selection in Sets. J. Comput. Syst. Sci. 37 (3) (1988)
Greg N. Frederickson
Fast Algorithms for Shortest Paths in Planar Graphs, with Applications. SIAM J. Comput. 16 (6) (1987)
Greg N. Frederickson
A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract) STOC (1987)
Greg N. Frederickson, Nancy A. Lynch
Electing a leader in a synchronous ring. J. ACM 34 (1) (1987)
Greg N. Frederickson
Upper Bounds for Time-Space Trade-Offs in Sorting and Selection. J. Comput. Syst. Sci. 34 (1) (1987)
Greg N. Frederickson, Mandayan A. Srinivas
On-line Updating of Solutions to a Class of Matroid Intersection Problems Inf. Comput. 74 (2) (1987)
Mikhail J. Atallah, Greg N. Frederickson
A note on finding a maximum empty rectangle. Discret. Appl. Math. 13 (1) (1986)
Greg N. Frederickson, Nicola Santoro
Breaking Symmetry in Synchronous Networks. Aegean Workshop on Computing (1986)
Greg N. Frederickson, Ravi Janardan
Separator-Based Strategies for Efficient Message Routing (Preliminary Version) FOCS (1986)
Greg N. Frederickson, Ravi Janardan
Optimal Message Routing without Complete Routing Tables (preliminary version). PODC (1986)
Greg N. Frederickson
Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. SIAM J. Comput. 14 (4) (1985)
Greg N. Frederickson
Implicit Data Structures for Weighted Elements Inf. Control. 66 (1/2) (1985)
Greg N. Frederickson
A Single Source Shortest Path Algorithm for a Planar Distributed Network. STACS (1985)
Edward G. Coffman Jr., Greg N. Frederickson, George S. Lueker
A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors. Math. Oper. Res. 9 (2) (1984)
Greg N. Frederickson, Donald B. Johnson
Generalized Selection and Ranking: Sorted Matrices. SIAM J. Comput. 13 (1) (1984)
Greg N. Frederickson
Self-Organizing Heuristics for Implicit Data Structures. SIAM J. Comput. 13 (2) (1984)
Greg N. Frederickson
Recursively Rotated Orders and Implicit Data Structures: A Lower Bound. Theor. Comput. Sci. 29 (1984)
Greg N. Frederickson, Nancy A. Lynch
The Impact of Synchronous Communication on the Problem of Electing a Leader in a Ring STOC (1984)
Greg N. Frederickson, Mandayam A. Srinivas
Data Structures for On-Line Updating of Matroid Intersection Solutions (Preliminary Version) STOC (1984)
Greg N. Frederickson
On Linear-Time Algorithms for Five-Coloring Planar Graphs. Inf. Process. Lett. 19 (5) (1984)
Greg N. Frederickson, Donald B. Johnson
Finding k-th Paths and p-Centers by Generating and Searching Good Data Structures. J. Algorithms 4 (1) (1983)
Greg N. Frederickson
Shortest Path Problems in Planar Graphs (Preliminary Version) FOCS (1983)
Greg N. Frederickson
Data Structures for On-Line Updating of Minimum Spanning Trees (Preliminary Version) STOC (1983)
Greg N. Frederickson
Implicit Data Structures for the Dictionary Problem J. ACM 30 (1) (1983)
Greg N. Frederickson
Tradeoffs for Selection in Distributed Networks (Preliminary Version). PODC (1983)
Greg N. Frederickson
Scheduling Unit-Time Tasks With Integer Release Times and Deadlines. Inf. Process. Lett. 16 (4) (1983)
Greg N. Frederickson, Donald B. Johnson
The Complexity of Selection and Ranking in X+Y and Matrices with Sorted Columns. J. Comput. Syst. Sci. 24 (2) (1982)
Greg N. Frederickson, Joseph F. JáJá
On the Relationship between the Biconnectivity Augmentation and Traveling Salesman Problems. Theor. Comput. Sci. 19 (1982)
Greg N. Frederickson
Implicit Data Structures for the Weighted Dictionary Problem (preliminary version) FOCS (1981)
Greg N. Frederickson, Joseph F. JáJá
Approximation Algorithms for Several Graph Augmentation Problems. SIAM J. Comput. 10 (2) (1981)
John L. Bruno, Peter J. Downey, Greg N. Frederickson
Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan. J. ACM 28 (1) (1981)
Greg N. Frederickson
Probabilistic Analysis for Simple One- and Two-Dimensional Bin Packing Algorithms. Inf. Process. Lett. 11 (4/5) (1980)
Greg N. Frederickson, Donald B. Johnson
Generalized Selection and Ranking (Preliminary Version) STOC (1980)
Greg N. Frederickson, Donald B. Johnson
Generating and Searching Sets Induced by Networks. ICALP (1980)
Greg N. Frederickson
Implicit Data Structures with Fast Update (Preliminary Report) FOCS (1980)
Greg N. Frederickson
Approximation Algorithms for Some Postman Problems. J. ACM 26 (3) (1979)
Greg N. Frederickson, Matthew S. Hecht, Chul E. Kim
Approximation Algorithms for Some Routing Problems. SIAM J. Comput. 7 (2) (1978)
Greg N. Frederickson, Matthew S. Hecht, Chul E. Kim
Approximation Algorithms for some Routing Problems FOCS (1976)