# Mordecai J. Golin

According to our database

Collaborative distances :

^{1}, Mordecai J. Golin authored at least 117 papers between 1988 and 2018.Collaborative distances :

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2018

Smoothed Analysis of the Expected Number of Maximal Points in Two Dimensions.

CoRR, 2018

Dynamic Trees with Almost-Optimal Access Cost.

CoRR, 2018

Minmax-Regret k-Sink Location on a Dynamic Tree Network with Uniform Capacities.

CoRR, 2018

Minmax Centered k-Partitioning of Trees and Applications to Sink Evacuation with Dynamic Confluent Flows.

CoRR, 2018

Dynamic Trees with Almost-Optimal Access Cost.

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems.

CoRR, 2017

Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks.

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems.

Proceedings of the 28th International Symposium on Algorithms and Computation, 2017

2016

Encoding 2D range maximum queries.

Theor. Comput. Sci., 2016

The channel capacity of read/write isolated memory.

Discrete Applied Mathematics, 2016

Minmax Tree Facility Location and Sink Evacuation with Dynamic Confluent Flows.

CoRR, 2016

Improved Algorithms for Computing k-Sink on Dynamic Path Networks.

CoRR, 2016

Optimal Evacuation Flows on Dynamic Paths with General Edge Capacities.

CoRR, 2016

Sink Evacuation on Trees with Dynamic Confluent Flows.

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

2015

Multiple sink location problems in dynamic path networks.

Theor. Comput. Sci., 2015

Minimax regret 1-sink location problem in dynamic path networks.

Theor. Comput. Sci., 2015

Optimal search trees with equality tests.

CoRR, 2015

Optimal Search Trees with 2-Way Comparisons.

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Scheduling with Gaps: New Models and Algorithms.

Proceedings of the Algorithms and Complexity - 9th International Conference, 2015

2014

Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity.

J. Graph Algorithms Appl., 2014

Improved Algorithms for Multiple Sink Location Problems in Dynamic Path Networks.

CoRR, 2014

Scheduling with Gaps: New Models and Algorithms.

CoRR, 2014

A Polynomial Time Algorithm for Minimax-Regret Evacuation on a Dynamic Path.

CoRR, 2014

Minimax Regret Sink Location Problem in Dynamic Tree Networks with Uniform Capacity.

Proceedings of the Algorithms and Computation - 8th International Workshop, 2014

Multiple Sink Location Problems in Dynamic Path Networks.

Proceedings of the Algorithmic Aspects in Information and Management, 2014

2013

Paging mobile users in cellular networks: Optimality versus complexity and simplicity.

Theor. Comput. Sci., 2013

2012

Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme.

SIAM J. Comput., 2012

Vehicle Scheduling on a Graph Revisited.

Proceedings of the Algorithms and Computation - 23rd International Symposium, 2012

2011

Encoding 2-D Range Maximum Queries

CoRR, 2011

Encoding 2D Range Maximum Queries.

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

2010

A dynamic programming approach to length-limited Huffman coding: space reduction with the Monge property.

IEEE Trans. Information Theory, 2010

The asymptotic number of spanning trees in circulant graphs.

Discrete Mathematics, 2010

Multidimensional Divide-and-Conquer and Weighted Digital Sums

CoRR, 2010

2009

The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity.

ACM Trans. Algorithms, 2009

Online Dynamic Programming Speedups.

Theory Comput. Syst., 2009

A generic top-down dynamic-programming approach to prefix-free coding.

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Multidimensional Divide-and-Conquer and Weighted Digital Sums.

Proceedings of the Sixth Workshop on Analytic Algorithmics and Combinatorics, 2009

2008

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding.

IEEE Trans. Information Theory, 2008

The number of spanning trees in a class of double fixed-step loop networks.

Networks, 2008

A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding

CoRR, 2008

A Dynamic Programming Approach To Length-Limited Huffman Coding

CoRR, 2008

2007

The two-median problem on Manhattan meshes.

Networks, 2007

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding

CoRR, 2007

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding.

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Paging Mobile Users Efficiently and Optimally.

Proceedings of the INFOCOM 2007. 26th IEEE International Conference on Computer Communications, 2007

The Asymptotic Number of Spanning Trees in Circulant Graphs.

Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics, 2007

2006

Online Maintenance of k-Medians and k-Covers on a Line.

Algorithmica, 2006

Online Dynamic Programming Speedups.

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Permanents of Circulants: A Transfer Matrix Approach.

Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005

Chebyshev polynomials and spanning tree formulas for circulant and related graphs.

Discrete Mathematics, 2005

Curve reconstruction from noisy samples.

Comput. Geom., 2005

The Structure of Optimal Prefix-Free Codes in Restricted Languages: The Uniform Probability Case.

Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Generalizing the Kraft-McMillan Inequality to Restricted Languages.

Proceedings of the 2005 Data Compression Conference (DCC 2005), 2005

Counting Structures in Grid Graphs, Cylinders and Tori Using Transfer Matrices: Survey and New Results.

Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, 2005

2004

Competitive facility location: the Voronoi game.

Theor. Comput. Sci., 2004

Finding optimal paths in MREP routing.

Inf. Process. Lett., 2004

New upper and lower bounds on the channel capacity of read/write isolated memory.

Discrete Applied Mathematics, 2004

Fun-Sort--or the chaos of unordered binary search.

Discrete Applied Mathematics, 2004

Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters.

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

Online Maintenance of k-Medians and k-Covers on a Line.

Proceedings of the Algorithm Theory, 2004

Algorithms for infinite huffman-codes.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Counting Spanning Trees and Other Structures in Non-constant-jump Circulant Graphs.

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

2003

Meeting the Welch and Karystinos-Pados Bounds on DS-CDMA Binary Signature Sets.

Des. Codes Cryptography, 2003

On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes.

Comput. Geom., 2003

Maximum residual energy routing with reverse energy cost.

Proceedings of the Global Telecommunications Conference, 2003

Recurrence Relations on Transfer Matrices Yield Good Lower and Upper Bounds on the Channel Capacity of Some 2-Dimensional Constrained Systems (Extended Abstract).

Proceedings of the 2003 Data Compression Conference (DCC 2003), 2003

Curve reconstruction from noisy samples.

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

2002

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property.

J. Algorithms, 2002

Prefix Codes: Equiprobable Words, Unequal Letter Costs

CoRR, 2002

Huffman Coding with Unequal Letter Costs

CoRR, 2002

Huffman coding with unequal letter costs.

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The Convex Hull for Random Lines in the Plane.

Proceedings of the Discrete and Computational Geometry, Japanese Conference, 2002

New Techniques for Bounding the Channel Capacity of Read/Write Isolated Memor.

Proceedings of the 2002 Data Compression Conference (DCC 2002), 2002

The probabilistic complexity of the Voronoi diagram of points on a polyhedron.

Proceedings of the 18th Annual Symposium on Computational Geometry, Barcelona, 2002

2001

A combinatorial approach to Golomb forests.

Theor. Comput. Sci., 2001

Lopsided Trees, I: Analyses.

Algorithmica, 2001

Protection of Keys against Modification Attack.

Proceedings of the 2001 IEEE Symposium on Security and Privacy, 2001

Optimal Prefix-Free Codes That End in a Specified Pattern and Similar Problems: The Uniform Probability Case.

Proceedings of the Data Compression Conference, 2001

Competitive Facility Location along a Highway.

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

2000

A dynamic programming algorithm for constructing optimal "1"-ended binary prefix-free codes.

IEEE Trans. Information Theory, 2000

An algorithm for finding a k-median in a directed tree.

Inf. Process. Lett., 2000

The number of spanning trees in circulant graphs.

Discrete Mathematics, 2000

On the Average Complexity of 3D-Voronoi Diagrams of Random Points on Convex Polytopes.

Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999

Optimal Point-to-point Broadcast Algorithms Via Lopsided Trees.

Discrete Applied Mathematics, 1999

On the Optimal Placement of Web Proxies in the Internet.

Proceedings of the Proceedings IEEE INFOCOM '99, 1999

1998

A Dynamic Programming Algorithm for Constructing Optimal Prefix-Free Codes with Unequal Letter Costs.

IEEE Trans. Information Theory, 1998

Labelled Trees and Pairs of Input-Output Permutations in Priority Queues.

Theor. Comput. Sci., 1998

Randomized Data Structures for the Dynamic Closest-Pair Problem.

SIAM J. Comput., 1998

Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems.

Int. J. Comput. Geometry Appl., 1998

On the Optimal Placement of Web Proxies in the Internet: The Linear Topology.

Proceedings of the High Performance Networking, 1998

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property.

Proceedings of the Algorithms, 1998

1997

Optimal point-to-point broadcast algorithms via lopsided trees.

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

1996

Prefix Codes: Equiprobable Words, Unequal Letter Costs.

SIAM J. Comput., 1996

Queries on Voronoi Diagrams of Moving Points.

Comput. Geom., 1996

Limit Theorems for Minimum-Weight Triangulations, Other Euclidean Functionals, and Probabilistic Recurrence Relations (Extended Abstract).

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Lopsided Trees: Analyses, Algorithms, and Applications.

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

Simple Randomized Algorithms for Closest Pair Problems.

Nord. J. Comput., 1995

Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas.

Inf. Process. Lett., 1995

A Dynamic Programming Algorithm for Constructing Optimal Refix-Free Codes for Unequal Letter Costs.

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

The Multi-Weighted Spanning Tree Problem (Extended Abstract).

Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994

Newton's Method for Quadratics, and Nested Intervals.

Complex Systems, 1994

A Provably Fast Linear-Expected-Time Maxima-Finding Algorithm.

Algorithmica, 1994

Mellin Transforms and Asymptotics: The Mergesort Recurrence.

Acta Inf., 1994

Labelled Trees and Pairs of Input-Output Permutations in Priority Queues.

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1994

Prefix Codes: Equiprobable Words, Unequal Letter Costs.

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Revenge of the Dog: Queries on Voronoi Diagrams of Moving Points.

Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

Incremental Algorithms for Finding the Convex Hulls of Circles and the Lower Envelopes of Parabolas.

Proceedings of the 6th Canadian Conference on Computational Geometry, 1994

1993

Queue-Mergesort.

Inf. Process. Lett., 1993

Randomized Data Structures for the Dynamic Closest-Pair Problem.

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Maxima in Convex Regions.

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Exact Asymptotics of Divide-and-Conquer Recurrences.

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Dog Bites Postman: Point Location in the Moving Voronoi Diagram and Related Problems.

Proceedings of the Algorithms - ESA '93, First Annual European Symposium, Bad Honnef, Germany, September 30, 1993

Simple Randomized Algorithms for Closest Pair Problems.

Proceedings of the 5th Canadian Conference on Computational Geometry, 1993

1992

How Many Maxima Can There Be?

Comput. Geom., 1992

Dynamic Closest Pairs - A Probabilistic Approach.

Proceedings of the Algorithm Theory, 1992

1988

Analysis of a Simple Yet Efficient Convex Hull Algorithm.

Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988