Alan M. Frieze

According to our database1, Alan M. Frieze authored at least 333 papers between 1974 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Pattern Colored Hamilton Cycles in Random Graphs.
SIAM J. Discrete Math., 2019

Perfect matchings and Hamiltonian cycles in the preferential attachment model.
Random Struct. Algorithms, 2019

A note on the localization number of random graphs: Diameter two case.
Discrete Applied Mathematics, 2019

On the rank of a random binary matrix.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights.
SIAM J. Discrete Math., 2018

Elegantly Colored Paths and Cycles in Edge Colored Random Graphs.
SIAM J. Discrete Math., 2018

A note on dispersing particles on a line.
Random Struct. Algorithms, 2018

Online purchasing under uncertainty.
Random Struct. Algorithms, 2018

A greedy algorithm for finding a large 2-matching on a random cubic graph.
Journal of Graph Theory, 2018

Balanced allocation through random walk.
Inf. Process. Lett., 2018

On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph.
Combinatorics, Probability & Computing, 2018

Packing Hamilton Cycles Online.
Combinatorics, Probability & Computing, 2018

On Rainbow Hamilton Cycles in Random Hypergraphs.
Electr. J. Comb., 2018

Constraining the Clustering Transition for Colorings of Sparse Random Graphs.
Electr. J. Comb., 2018

The Cover Time of a Biased Random Walk on a Random Cubic Graph.
Proceedings of the 29th International Conference on Probabilistic, 2018

The cover time of a biased random walk on Gn, p.
Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, 2018

2017
Minimum Cost Matching in a Random Graph with Random Costs.
SIAM J. Discrete Math., 2017

On random k-out subgraphs of large graphs.
Random Struct. Algorithms, 2017

Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity.
J. Comb. Theory, Ser. B, 2017

Randomly coloring simple hypergraphs with fewer colors.
Inf. Process. Lett., 2017

On the insertion time of random walk cuckoo hashing.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Traveling in Randomly Embedded Random Graphs.
Proceedings of the Approximation, 2017

2016
Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk.
SIAM J. Discrete Math., 2016

Rainbow matchings and Hamilton cycles in random graphs.
Random Struct. Algorithms, 2016

Rainbow Arborescence in Random Digraphs.
Journal of Graph Theory, 2016

On the Length of a Random Minimum Spanning Tree.
Combinatorics, Probability & Computing, 2016

Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs.
Electr. J. Comb., 2016

Separating subadditive euclidean functionals.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Discordant Voting Processes on Finite Graphs.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Walker-Breaker Games.
SIAM J. Discrete Math., 2015

Rainbow Connection of Random Regular Graphs.
SIAM J. Discrete Math., 2015

Efficient algorithms for three-dimensional axial and planar random assignment problems.
Random Struct. Algorithms, 2015

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three.
Random Struct. Algorithms, 2015

On the chromatic number of a random hypergraph.
J. Comb. Theory, Ser. B, 2015

Long Paths in Random Apollonian Networks.
Internet Mathematics, 2015

Loose Hamilton Cycles in Regular Hypergraphs.
Combinatorics, Probability & Computing, 2015

Between 2- and 3-Colorability.
Electr. J. Comb., 2015

On-line List Colouring of Random Graphs.
Electr. J. Comb., 2015

Power of k Choices and Rainbow Spanning Trees in Random Graphs.
Electr. J. Comb., 2015

2014
Expanders via Random Spanning Trees.
SIAM J. Comput., 2014

Rainbow hamilton cycles in random graphs.
Random Struct. Algorithms, 2014

On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three.
Random Struct. Algorithms, 2014

The height of random k-trees and related branching processes.
Random Struct. Algorithms, 2014

Cover time of a random graph with a degree sequence II: Allowing vertices of degree two.
Random Struct. Algorithms, 2014

Maker-breaker games on random geometric graphs.
Random Struct. Algorithms, 2014

Some Properties of Random Apollonian Networks.
Internet Mathematics, 2014

The t-Tone Chromatic Number of Random Graphs.
Graphs and Combinatorics, 2014

The Topology of Competitively Constructed Graphs.
Electr. J. Comb., 2014

Packing Tree Factors in Random and Pseudo-random Graphs.
Electr. J. Comb., 2014

2013
The cover times of random walks on random uniform hypergraphs.
Theor. Comput. Sci., 2013

On the Game Chromatic Number of Sparse Random Graphs.
SIAM J. Discrete Math., 2013

Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010).
SIAM J. Comput., 2013

Tight Hamilton cycles in random uniform hypergraphs.
Random Struct. Algorithms, 2013

Coloring simple hypergraphs.
J. Comb. Theory, Ser. B, 2013

Approximate counting of regular hypergraphs.
Inf. Process. Lett., 2013

Special Issue on Algorithms and Models for the Web Graph.
Internet Mathematics, 2013

On the Non-Planarity of a Random Subgraph.
Combinatorics, Probability & Computing, 2013

Algorithmic techniques for modeling and mining large graphs (AMAzING).
Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013

2012
Packing Tight Hamilton Cycles in Uniform Hypergraphs.
SIAM J. Discrete Math., 2012

Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables.
Random Struct. Algorithms, 2012

Packing hamilton cycles in random and pseudo-random hypergraphs.
Random Struct. Algorithms, 2012

Variations on cops and robbers.
Journal of Graph Theory, 2012

Stationary distribution and cover time of random walks on random digraphs.
J. Comb. Theory, Ser. B, 2012

Cover time of a random graph with given degree sequence.
Discrete Mathematics, 2012

Cops and Robbers on Geometric Graphs.
Combinatorics, Probability & Computing, 2012

Rainbow Connection of Sparse Random Graphs.
Electr. J. Comb., 2012

Optimal Divisibility Conditions for Loose Hamilton Cycles in Random Hypergraphs.
Electr. J. Comb., 2012

Rainbow Hamilton Cycles in Uniform Hypergraphs.
Electr. J. Comb., 2012

On Certain Properties of Random Apollonian Networks.
Proceedings of the Algorithms and Models for the Web Graph - 9th International Workshop, 2012

Some Typical Properties of the Spatial Preferred Attachment Model.
Proceedings of the Algorithms and Models for the Web Graph - 9th International Workshop, 2012

Rainbow Connectivity of Sparse Random Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

Analyzing Walksat on Random Formulas.
Proceedings of the 9th Meeting on Analytic Algorithmics and Combinatorics, 2012

2011
Ramsey games with giants.
Random Struct. Algorithms, 2011

Randomly coloring simple hypergraphs.
Inf. Process. Lett., 2011

Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011

Karp-Sipser on Random Graphs with a Fixed Degree Sequence.
Combinatorics, Probability & Computing, 2011

Loose Hamilton Cycles in Random Uniform Hypergraphs.
Electr. J. Comb., 2011

Packing tight Hamilton cycles in 3-uniform hypergraphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Component structure of the vacant set induced by a random walk on a random graph.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Cover Times of Random Walks on Hypergraphs.
Proceedings of the Structural Information and Communication Complexity, 2011

2010
Hamilton Cycles in Random Graphs with a Fixed Degree Sequence.
SIAM J. Discrete Math., 2010

Random Walks with Look-Ahead in Scale-Free Random Graphs.
SIAM J. Discrete Math., 2010

Flips in Graphs.
SIAM J. Discrete Math., 2010

Randomly coloring random graphs.
Random Struct. Algorithms, 2010

Coloring H-free hypergraphs.
Random Struct. Algorithms, 2010

Anti-Ramsey properties of random graphs.
J. Comb. Theory, Ser. B, 2010

Finding a maximum matching in a sparse random graph in O(n) expected time.
J. ACM, 2010

Loose Hamilton Cycles in Random 3-Uniform Hypergraphs.
Electr. J. Comb., 2010

Hypergraphs with independent neighborhoods.
Combinatorica, 2010

2009
Multiple Random Walks in Random Regular Graphs.
SIAM J. Discrete Math., 2009

Memoryless Rules for Achlioptas Processes.
SIAM J. Discrete Math., 2009

Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401-439.
Random Struct. Algorithms, 2009

Hamilton cycles in 3-out.
Random Struct. Algorithms, 2009

The cover time of random geometric graphs.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

On smoothed k-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

An efficient sparse regularity concept.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Multiple Random Walks and Interacting Particle Systems.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

An Analysis of Random-Walk Cuckoo Hashing.
Proceedings of the Approximation, 2009

Average-Case Analyses of Vickrey Costs.
Proceedings of the Approximation, 2009

2008
Game chromatic index of graphs with given restrictions on degrees.
Theor. Comput. Sci., 2008

Hamilton Cycles in Random Lifts of Directed Graphs.
SIAM J. Discrete Math., 2008

The cover time of the giant component of a random graph.
Random Struct. Algorithms, 2008

The game chromatic number of random graphs.
Random Struct. Algorithms, 2008

On the Chromatic Number of Simple Triangle-Free Triple Systems.
Electr. J. Comb., 2008

On Rainbow Trees and Cycles.
Electr. J. Comb., 2008

Random k-SAT: The Limiting Probability for Satisfiability for Moderately Growing k.
Electr. J. Comb., 2008

Logconcave random graphs.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Random Walks on Random Graphs.
Proceedings of the Nano-Net - Third International ICST Conference, 2008

Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

A new approach to the planted clique problem.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

2007
The diameter of randomly perturbed digraphs and some applications.
Random Struct. Algorithms, 2007

Randomly generated intersecting hypergraphs II.
Random Struct. Algorithms, 2007

The cover time of the preferential attachment graph.
J. Comb. Theory, Ser. B, 2007

The Influence of Search Engines on Preferential Attachment.
Internet Mathematics, 2007

Codes identifying sets of vertices in random networks.
Discrete Mathematics, 2007

On the Chromatic Number of Random Graphs with a Fixed Degree Sequence.
Combinatorics, Probability & Computing, 2007

First-Order Definability of Trees and Sparse Random Graphs.
Combinatorics, Probability & Computing, 2007

Random 2-SAT with Prescribed Literal Degrees.
Algorithmica, 2007

A Geometric Preferential Attachment Model of Networks II.
Proceedings of the Algorithms and Models for the Web-Graph, 5th International Workshop, 2007

Line-of-sight networks.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Separating Populations with Wide Data: A Spectral Analysis.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

The Cover Time of Random Digraphs.
Proceedings of the Approximation, 2007

2006
Almost universal graphs.
Random Struct. Algorithms, 2006

Randomly coloring sparse random graphs with fewer colors than the maximum degree.
Random Struct. Algorithms, 2006

Hamilton cycles in random lifts of graphs.
Eur. J. Comb., 2006

On randomly colouring locally sparse graphs.
Discrete Mathematics & Theoretical Computer Science, 2006

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

2005
The Strong Chromatic Index of Random Graphs.
SIAM J. Discrete Math., 2005

The Cover Time of Random Regular Graphs.
SIAM J. Discrete Math., 2005

Perfect matchings in random bipartite graphs with minimal degree at least 2.
Random Struct. Algorithms, 2005

On packing Hamilton cycles in ?-regular graphs.
J. Comb. Theory, Ser. B, 2005

Random k-Sat: A Tight Threshold For Moderately Growing k.
Combinatorica, 2005

On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Adversarial deletion in a scale free random graph process.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On the random 2-stage minimum spanning tree.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The cover time of two classes of random graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

The influence of search engines on preferential attachment.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Identifying codes in random networks.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005

2004
The emergence of a giant component in random subgraphs of pseudo-random graphs.
Random Struct. Algorithms, 2004

Avoidance of a giant component in half the edge set of a random graph.
Random Struct. Algorithms, 2004

Adding random edges to dense graphs.
Random Struct. Algorithms, 2004

Clustering Large Graphs via the Singular Value Decomposition.
Machine Learning, 2004

Efficient communication in an ad-hoc network.
J. Algorithms, 2004

Randomly coloring constant degree graphs
Electronic Colloquium on Computational Complexity (ECCC), 2004

The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence.
Combinatorics, Probability & Computing, 2004

On the b-Independence Number of Sparse Random Graphs.
Combinatorics, Probability & Computing, 2004

A Geometric Preferential Attachment Model of Networks.
Proceedings of the Algorithms and Models for the Web-Graph: Third International Workshop, 2004

Randomly Coloring Constant Degree Graphs.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

The Diameter of Randomly Perturbed Digraphs and Some Applications..
Proceedings of the Approximation, 2004

2003
A probabilistic analysis of randomly generated binary constraint satisfaction problems.
Theor. Comput. Sci., 2003

Randomly coloring graphs with lower bounds on girth and maximum degree.
Random Struct. Algorithms, 2003

A general model of web graphs.
Random Struct. Algorithms, 2003

How many random edges make a dense graph hamiltonian?
Random Struct. Algorithms, 2003

Random Deletion in a Scale-Free Random Graph Process.
Internet Mathematics, 2003

Crawling on Simple Models of Web Graphs.
Internet Mathematics, 2003

On Randomly Generated Intersecting Hypergraphs.
Electr. J. Comb., 2003

Perfect matchings in random graphs with prescribed minimal degree.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

The cover time of sparse random graphs.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems.
Proceedings of the Approximation, 2003

High Degree Vertices and Eigenvalues in the Preferential Attachment Graph.
Proceedings of the Approximation, 2003

Analytic Graph Theory.
Proceedings of the Handbook of Graph Theory., 2003

2002
Addendum to avoiding a giant component.
Random Struct. Algorithms, 2002

On graph irregularity strength.
Journal of Graph Theory, 2002

Hamilton cycles in random subgraphs of pseudo-random graphs.
Discrete Mathematics, 2002

Random Regular Graphs Of Non-Constant Degree: Independence And Chromatic Number.
Combinatorics, Probability & Computing, 2002

Random Regular Graphs Of Non-Constant Degree: Connectivity And Hamiltonicity.
Combinatorics, Probability & Computing, 2002

Multi-Coloured Hamilton Cycles In Random Edge-Coloured Graphs.
Combinatorics, Probability & Computing, 2002

Crawling on web graphs.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Balls and bins models with feedback.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

A note on random 2-SAT with prescribed literal degrees.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

On Random Symmetric Travelling Salesman Problems.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Hamilton cycles in the union of random permutations.
Random Struct. Algorithms, 2001

Avoiding a giant component.
Random Struct. Algorithms, 2001

On Markov Chains for Randomly H-Coloring a Graph.
J. Algorithms, 2001

A general approach to dynamic packet routing with bounded buffers.
J. ACM, 2001

G-Intersecting Families.
Combinatorics, Probability & Computing, 2001

Vertex Covers by Edge Disjoint Cliques.
Combinatorica, 2001

The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Optimal sequencing by hybridization in rounds.
Proceedings of the Fifth Annual International Conference on Computational Biology, 2001

Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Arc-Disjoint Paths in Expander Digraphs.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

A General Model of Undirected Web Graphs.
Proceedings of the Algorithms, 2001

2000
Hamilton cycles in random graphs and directed graphs.
Random Struct. Algorithms, 2000

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k.
Journal of Graph Theory, 2000

Min-Wise Independent Permutations.
J. Comput. Syst. Sci., 2000

A Note on Random Minimum Length Spanning Trees.
Electr. J. Comb., 2000

On the Number of Perfect Matchings and Hamilton Cycles in e-Regular Non-bipartite Graphs.
Electr. J. Comb., 2000

Note on Sparse Random Graphs and Cover Graphs.
Electr. J. Comb., 2000

Min-Wise Independent Linear Permutations.
Electr. J. Comb., 2000

Edge-disjoint paths in expander graphs.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
On Perfect Matchings and Hamilton Cycles in Sums of Random Trees.
SIAM J. Discrete Math., 1999

Mixing properties of the Swendsen-Wang process on classes of graphs.
Random Struct. Algorithms, 1999

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach.
Random Struct. Algorithms, 1999

Optimal Reconstruction of a Sequence from its Probes.
Journal of Computational Biology, 1999

Splitting an Expander Graph.
J. Algorithms, 1999

A Simple Algorithm for Constructing Szemere'di's Regularity Partition.
Electr. J. Comb., 1999

Quick Approximation to Matrices and Applications.
Combinatorica, 1999

Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Clustering in Large Graphs and Matrices.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On the power of universal bases in sequencing by hybridization.
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999

On Counting Independent Sets in Sparse Graphs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Approximately Counting Hamilton Paths and Cycles in Dense Graphs.
SIAM J. Comput., 1998

Maximum matchings in sparse random graphs: Karp-Sipser revisited.
Random Struct. Algorithms, 1998

Random Minimum Length Spanning Trees in Regular Graphs.
Combinatorica, 1998

Average-Case Analysis of the Merging Algorithm of Hwang and Lin.
Algorithmica, 1998

Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal.
Algorithmica, 1998

Min-Wise Independent Permutations (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Disjoint Paths in Expander Graphs via Random Walks: A Short Survey.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

On Balls and Bins with Deletions.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Dynamic Packet Routing on Arrays with Bounded Buffers.
Proceedings of the LATIN '98: Theoretical Informatics, 1998

Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Algorithmic theory of random graphs.
Random Struct. Algorithms, 1997

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.
Algorithmica, 1997

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

1996
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph.
Random Struct. Algorithms, 1996

Analysis of Two Simple Heuristics on a Random Instance of k-SAT.
J. Algorithms, 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.
J. Algorithms, 1996

On the Best Case of Heapsort.
J. Algorithms, 1996

Perfect Matchings in Random r-regular, s-uniform Hypergraphs.
Combinatorics, Probability & Computing, 1996

An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Coloring Bipartite Hypergraphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

The Regularity Lemma and Approximation Schemes for Dense Problems.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Learning Linear Transformations.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal.
Proceedings of the Algorithms, 1996

1995
Perfect Matchings in Random s-Uniform Hypergraphs.
Random Struct. Algorithms, 1995

Randomized Greedy Matching II.
Random Struct. Algorithms, 1995

Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
Random Struct. Algorithms, 1995

On Key Storage in Secure Networks.
J. Cryptology, 1995

Ordering Clone Libraries in Computational Biology.
Journal of Computational Biology, 1995

Balanced Allocations for Tree-Like Inputs.
Inf. Process. Lett., 1995

The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.
Inf. Process. Lett., 1995

On the Connectivity of Random k-th Nearest Neighbour Graphs.
Combinatorics, Probability & Computing, 1995

Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold.
Electr. J. Comb., 1995

Multicoloured Hamilton Cycles.
Electr. J. Comb., 1995

Covering the Edges of a Random Graph by Cliques.
Combinatorica, 1995

An Analysis of a Monte Carlo Algorithm for Estimating the Permanent.
Combinatorica, 1995

Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995

1994
Existence and Construction of Edge-Disjoint Paths on Expander Graphs.
SIAM J. Comput., 1994

On the Independence Number of Random Cubic Graphs.
Random Struct. Algorithms, 1994

Multicolored Trees in Random Graphs.
Random Struct. Algorithms, 1994

Introduction.
Random Struct. Algorithms, 1994

Finding Hidden Hamiltonian Cycles.
Random Struct. Algorithms, 1994

Random walks, totally unimodular matrices, and a randomised dual simplex algorithm.
Math. Program., 1994

Hamilton Cycles in a Class of Random Directed Graphs.
J. Comb. Theory, Ser. B, 1994

The Probability of Unique Solutions of Sequencing by Hybridization.
Journal of Computational Biology, 1994

On the Problem of Approximating the Number of Bases of a Matroid.
Inf. Process. Lett., 1994

Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
Electronic Colloquium on Computational Complexity (ECCC), 1994

Broadcasting in Random Graphs.
Discrete Applied Mathematics, 1994

Hamilton Cycles in Random Regular Digraphs.
Combinatorics, Probability & Computing, 1994

On the Complexity of Computing the Diameter of a Polytope.
Computational Complexity, 1994

Approximately Counting Hamilton Cycles in Dense Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Optimal Construction of Edge-Disjoint Paths in Random Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

On the Greedy Heuristic for Matchings.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Polychromatic Hamilton cycles.
Discrete Mathematics, 1993

A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.
Combinatorics, Probability & Computing, 1993

Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

1992
Counting the Number of Hamilton Cycles in Random Digraphs.
Random Struct. Algorithms, 1992

On the Expected Performance of a Parallel Algorithm for Finding Maximal Independent Subsets of a Random Graph.
Random Struct. Algorithms, 1992

On the independence and chromatic numbers of random regular graphs.
J. Comb. Theory, Ser. B, 1992

On Subgraph Sizes in Random Graphs.
Combinatorics, Probability & Computing, 1992

Existence and Construction of Edge Disjoint Paths on Expander Graphs
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Separator Based Parallel Divide and Conquer in Computational Geometry.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

When is the Assignment Bound Tight for the Asymmetric Traveling Salesman Problem?
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

Near-perfect Token Distribution.
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991
Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph.
Random Struct. Algorithms, 1991

Randomized Greedy Matching.
Random Struct. Algorithms, 1991

Spanning Maximal Planar Subgraphs of Random Graphs.
Random Struct. Algorithms, 1991

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.
J. ACM, 1991

Occupancy problems and random algebras.
Discrete Mathematics, 1991

Finding Hidden Hamiltonian Cycles (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990
Greedy Matching on the Line.
SIAM J. Comput., 1990

Probabilistic Analysis of a Parallel Algorithm for Finding Maximal Independent Sets.
Random Struct. Algorithms, 1990

On Patching Algorithms for Random Asymmetric Travelling Salesman Problems.
Math. Program., 1990

The limiting probability that alpha-in, ß-out is strongly connected.
J. Comb. Theory, Ser. B, 1990

On the independence number of random graphs.
Discrete Mathematics, 1990

On an optimization problem with nested constraints.
Discrete Applied Mathematics, 1990

Probabilistic Analysis of the Generalised Assignment Problem.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

1989
Algorithms for assignment problems on an array processor.
Parallel Computing, 1989

A randomized algorithm for fixed-dimensional linear programming.
Math. Program., 1989

Probabilistic Analysis of the Multidimensional Knapsack Problem.
Math. Oper. Res., 1989

On the number of hamilton cycles in a random graph.
Journal of Graph Theory, 1989

The Solution of Some Random NP-Hard Problems in Polynomial Expected Time.
J. Algorithms, 1989

On random minimum lenght spanning trees.
Combinatorica, 1989

Survival time of a random graph.
Combinatorica, 1989

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
Reconstructing Truncated Integer Variables Satisfying Linear Congruences.
SIAM J. Comput., 1988

On the Complexity of Computing the Volume of a Polyhedron.
SIAM J. Comput., 1988

Probabilistic Analysis of a Relaxation for the k-Median Problem.
Math. Oper. Res., 1988

Edge-colouring random graphs.
J. Comb. Theory, Ser. B, 1988

Finding hamilton cycles in sparse random graphs.
J. Comb. Theory, Ser. B, 1988

An Algorithm for Finding Hamilton Cycles in Random Directed Graphs.
J. Algorithms, 1988

On the Random Construction of Heaps.
Inf. Process. Lett., 1988

Partitioning random graphs into large cycles.
Discrete Mathematics, 1988

1987
On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients.
SIAM J. Comput., 1987

Large induced trees in sparse random graphs.
J. Comb. Theory, Ser. B, 1987

Parallel Algorithms for Finding Hamilton Cycles in Random Graphs.
Inf. Process. Lett., 1987

Large holes in sparse random graphs.
Combinatorica, 1987

An algorithm for finding Hamilton cycles in a random graph.
Combinatorica, 1987

1986
On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem.
SIAM J. Comput., 1986

On linear programs with random costs.
Math. Program., 1986

Maximum matchings in a class of random graphs.
J. Comb. Theory, Ser. B, 1986

Planar 3DM is NP-Complete.
J. Algorithms, 1986

On large matchings and cycles in sparse random graphs.
Discrete Mathematics, 1986

Fast Solution of Some Random NP-Hard Problems
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
Limit Distribution for the Existence of Hamiltonian Cycles in Random Bipartite Graphs.
Eur. J. Comb., 1985

The shortest-path problem for graphs with random arc-lengths.
Discrete Applied Mathematics, 1985

On the value of a random minimum spanning tree problem.
Discrete Applied Mathematics, 1985

On the complexity of partitioning graphs into connected subgraphs.
Discrete Applied Mathematics, 1985

An Algorithm for Finding a Matroid Basis which Maximizes the Products of the Weights of the Elements.
BIT, 1985

An Algorithm for Finding Hamilton Cycles in a Random Graph
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984
Hamiltonian cycles in random regular graphs.
J. Comb. Theory, Ser. B, 1984

A Partitioning Algorithm for Minimum Weighted Euclidean Matching.
Inf. Process. Lett., 1984

Linear Congruential Generators Do Not Produce Random Sequences
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Corrigendum: Algebraic Linear Programming.
Math. Oper. Res., 1983

On the existence of Hamiltonian cycles in a class of random graphs.
Discrete Mathematics, 1983

On the quadratic assignment problem.
Discrete Applied Mathematics, 1983

An extension of Christofides heuristic to the k-person travelling salesman problem.
Discrete Applied Mathematics, 1983

1982
On the worst-case performance of some algorithms for the asymmetric traveling salesman problem.
Networks, 1982

Algebraic Linear Programming.
Math. Oper. Res., 1982

On the connectivity of random m-orientable graphs and digraphs.
Combinatorica, 1982

1980
Probabilistic analysis of some euclidean clustering problems.
Discrete Applied Mathematics, 1980

1979
An algorithm for algebraic assignment problems.
Discrete Applied Mathematics, 1979

1976
Shortest path algorithms for knapsack type problems.
Math. Program., 1976

1974
A bilinear programming formulation of the 3-dimensional assignment problem.
Math. Program., 1974

A cost function property for plant location problems.
Math. Program., 1974


  Loading...