Search filters

List of works by Alan M. Frieze

A Partitioned Inverse in Linear Programming

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions

A cost function property for plant location problems

scientific article published in 1974

A general approach to dynamic packet routing with bounded buffers

A general approach to dynamic packet routing with bounded buffers

A general model of web graphs

article

A new integer programming formulation for the permutation flowshop problem

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

A partitioning algorithm for minimum weighted Euclidean matching

A polynomial-time algorithm for learning noisy linear threshold functions

A probabilistic analysis of randomly generated binary constraint satisfaction problems

A probabilistic analysis of the next fit decreasing bin packing heuristic

A random polynomial-time algorithm for approximating the volume of convex bodies

article by Martin Dyer et al published 3 January 1991 in Journal of the ACM

A randomized algorithm for fixed-dimensional linear programming

Adding random edges to dense graphs

scholarly article by Tom Bohman et al published 2004 in Random Structures and Algorithms

Algebraic Linear Programming

scholarly article by A. M. Frieze published May 1982 in Mathematics of Operations Research

Almost universal graphs

scholarly article by Alan M. Frieze & Michael Krivelevich published 2006 in Random Structures and Algorithms

An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice

An Analysis of Random-Walk Cuckoo Hashing

An Efficient Sparse Regularity Concept

An algorithm for algebraic assignment problems

scholarly article by A.M. Frieze published December 1979 in Discrete Applied Mathematics

An algorithm for finding hamilton paths and cycles in random graphs

An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

scholarly article by Alan M. Frieze & Simi Haber published 10 April 2014 in Random Structures and Algorithms

An analysis of a Monte Carlo algorithm for estimating the permanent

article

An extension of Christofides heuristic to the k-person travelling salesman problem

Analysis of Two Simple Heuristics on a Random Instance ofk-sat

article

Analysis of heuristics for finding a maximum weight planar subgraph

Analyzing Walksat on Random Formulas

article

Anti-Ramsey properties of random graphs

Approximate counting of regular hypergraphs

scholarly article by Andrzej Dudek et al published September 2013 in Information Processing Letters

Approximately Counting Hamilton Paths and Cycles in Dense Graphs

Approximation algorithms for the m-dimensional 0–1 knapsack problem: Worst-case and probabilistic analyses

Arc-Disjoint Paths in Expander Digraphs

Arc-disjoint paths in expander digraphs

Average-Case Analysis of the Merging Algorithm of Hwang and Lin

Avoidance of a giant component in half the edge set of a random graph

article

Avoiding a giant component

scholarly article by Tom Bohman & Alan M. Frieze published 2001 in Random Structures and Algorithms

Balanced allocations for tree-like inputs

Bottleneck Linear Programming

Broadcasting in random graphs

Clustering Large Graphs via the Singular Value Decomposition

Codes identifying sets of vertices in random networks

Coloring H-free hypergraphs

scholarly article by Tom Bohman et al published January 2010 in Random Structures and Algorithms

Coloring simple hypergraphs

article by Alan M. Frieze & Dhruv Mubayi published November 2013 in Journal of Combinatorial Theory, Series B

Complexity of a 3-dimensional assignment problem

article published in 1983

Component structure of the vacant set induced by a random walk on a random graph

scholarly article by Colin Cooper & Alan M. Frieze published 8 February 2012 in Random Structures and Algorithms

Cops and Robbers on Geometric Graphs

Correction: Sampling from Log-Concave Distributions

Corrigendum: Algebraic Linear Programming

scholarly article published in Mathematics of Operations Research

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

scholarly article by Colin Cooper & Alan M. Frieze published March 2009 in Random Structures and Algorithms

Counting the Number of Hamilton Cycles in Random Digraphs

scholarly article by Alan M. Frieze & Stephen Suen published 1992 in Random Structures and Algorithms

Cover time of a random graph with a degree sequence II: Allowing vertices of degree two

scholarly article by Colin Cooper et al published December 2014 in Random Structures and Algorithms

Cover time of a random graph with given degree sequence

article published in 2012

Covering the edges of a random graph by cliques

Dynamic packet routing on arrays with bounded buffers

Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least k

scientific article published in 2000

Efficient algorithms for three-dimensional axial and planar random assignment problems

Efficient communication in an ad-hoc network

Embedding the Erdős–Rényi hypergraph into the random regular hypergraph and Hamiltonicity

Existence and Construction of Edge-Disjoint Paths on Expander Graphs

Expanders via Random Spanning Trees

Fast Monte-Carlo algorithms for finding low-rank approximations

scholarly article

Fast monte-carlo algorithms for finding low-rank approximations

scholarly article by Alan M. Frieze et al published 1 November 2004 in Journal of the ACM

Finding a maximum matching in a sparse random graph inO(n) expected time

article published in 2010

First-Order Definability of Trees and Sparse Random Graphs

Flips in Graphs

Game chromatic index of graphs with given restrictions on degrees

Generating and Counting Hamilton Cycles in Random Regular Graphs

article

Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal

Greedy Matching on the Line

Hamilton Cycles in Random Graphs with a Fixed Degree Sequence

Hamilton Cycles in Random Lifts of Directed Graphs

Hamilton Cycles in a Class of Random Directed Graphs

article published in 1994

Hamilton cycles in 3-out

scholarly article by Tom Bohman & Alan M. Frieze published December 2009 in Random Structures and Algorithms

Hamilton cycles in random lifts of graphs

Hamilton cycles in random subgraphs of pseudo-random graphs

How many random edges make a dense graph hamiltonian?

scholarly article by Tom Bohman et al published 8 November 2002 in Random Structures and Algorithms

Hypergraphs with independent neighborhoods

Improved approximation algorithms for MAXk-CUT and MAX BISECTION

scholarly article by Alan M. Frieze & M. Jerrum published May 1997 in Algorithmica

Introduction

scholarly article by Alan M. Frieze et al published January 1994 in Random Structures and Algorithms

Karp–Sipser on Random Graphs with a Fixed Degree Sequence

Large holes in sparse random graphs

scientific article

Learning linear transformations

Line-of-Sight Networks

article by Alan M. Frieze et al published 12 August 2008 in Combinatorics, Probability and Computing

Linear and combinatorial optimization in ordered algebraic structures

scholarly article by A.M. Frieze published May 1982 in European Journal of Operational Research

Log-Sobolev inequalities and sampling from log-concave distributions

scientific article published in 1999

Long Paths in Random Apollonian Networks

Loose Hamilton Cycles in Regular Hypergraphs

Maker-breaker games on random geometric graphs

scholarly article by Andrew Beveridge et al published December 2014 in Random Structures and Algorithms

Maximum matchings in a class of random graphs

Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables

article by Alan M. Frieze & Páll Melsted published 7 May 2012 in Random Structures and Algorithms

Memoryless Rules for Achlioptas Processes

Min-Wise Independent Permutations

Minimum Paths in Directed Graphs

Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs

article by COLIN COOPER & Alan M. Frieze published March 2002 in Combinatorics, Probability and Computing

Multicolored trees in random graphs

scholarly article by Alan M. Frieze & Brendan McKay published January 1994 in Random Structures and Algorithms

Multiple Random Walks in Random Regular Graphs

Near-perfect token distribution

scholarly article by A. Z. Broder et al published October 1994 in Random Structures and Algorithms

On Bottleneck Linear Programming

On Counting Independent Sets in Sparse Graphs

On Perfect Matchings and Hamilton Cycles in Sums of Random Trees

On Random Symmetric Travelling Salesman Problems

On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three

article by Alan M. Frieze published 27 December 2012 in Random Structures and Algorithms

On an optimization problem with nested constraints

On graph irregularity strength

On linear programs with random costs

On packing Hamilton cycles in ε -regular graphs

On patching algorithms for random asymmetric travelling salesman problems

On random minimum length spanning trees

article

On the $b$ -Independence Number of Sparse Random Graphs

On the Best Case of Heapsort

On the Chromatic Number of Random Graphs with a Fixed Degree Sequence

On the Complexity of Computing the Volume of a Polyhedron

article by Martin Dyer & Alan M. Frieze published October 1988 in SIAM Journal on Computing

On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients

On the Game Chromatic Number of Sparse Random Graphs

On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

On the Length of a Random Minimum Spanning Tree

On the Length of the Longest Monotone Subsequence in a Random Permutation

scientific article published in 1991

On the Non-Planarity of a Random Subgraph

On the Strength of Connectivity of Random Subgraphs of the n-Cube

On the chromatic number of a random hypergraph

On the complexity of partitioning graphs into connected subgraphs

On the connectivity of random m-orientable graphs and digraphs

article

On the existence of Hamiltonian cycles in a class of random graphs

On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph

scholarly article by Neil J. Calkin et al published 1992 in Random Structures and Algorithms

On the independence number of random cubic graphs

scholarly article by Alan M. Frieze & Stephen Suen published December 1994 in Random Structures and Algorithms

On the independence number of random graphs

On the number of hamilton cycles in a random graph

On the problem of approximating the number of bases of a matriod

On the quadratic assignment problem

On the random 2-stage minimum spanning tree

article

On the value of a random minimum spanning tree problem

article

On the worst-case performance of some algorithms for the asymmetric traveling salesman problem

scholarly article by A. M. Frieze et al published 1982 in Networks

On two Hamilton cycle problems in random graphs

Optimal reconstruction of a sequence from its probes.

scientific article published in September 1999

Optimal sequencing by hybridization in rounds

scientific article published in January 2002

Packing Tight Hamilton Cycles in Uniform Hypergraphs

Packing hamilton cycles in random and pseudo-random hypergraphs

Packing tight Hamilton cycles in 3-uniform hypergraphs

scholarly article by Alan M. Frieze et al published 28 June 2011 in Random Structures and Algorithms

Parallel algorithms for finding Hamilton cycles in random graphs

scholarly article by A.M. Frieze published May 1987 in Information Processing Letters

Partitioning random graphs into large cycles

Perfect matchings in random bipartite graphs with minimal degree at least 2

article

Perfect matchings in random s-uniform hypergraphs

scholarly article by Alan M. Frieze & Svante Janson published August 1995 in Random Structures and Algorithms

Polychromatic Hamilton cycles

Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case

scientific article (publication date: July 1995)

Probabilistic Analysis of a Relaxation for thek-Median Problem

Probabilistic Analysis of an Algorithm in the Theory of Markets in Indivisible Goods

Probabilistic Analysis of the Multidimensional Knapsack Problem

Probabilistic analysis of some euclidean clustering problems

Probabilistic analysis of the generalised assignment problem

Product rule wins a competitive game

Quick Approximation to Matrices and Applications

Rainbow Arborescence in Random Digraphs

article by Deepak Bal et al published 7 October 2015 in Journal of Graph Theory

Rainbow hamilton cycles in random graphs

scholarly article by Alan M. Frieze & Po-Shen Loh published 13 February 2013 in Random Structures and Algorithms

Rainbow matchings and Hamilton cycles in random graphs

article by Deepak Bal & Alan M. Frieze published 6 July 2015 in Random Structures and Algorithms

Ramsey games with giants

Random 2-SAT with Prescribed Literal Degrees

Random Minimum Length Spanning Trees in Regular Graphs

Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity

Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number

Random Walks with Look-Ahead in Scale-Free Random Graphs

Random graphs

Random triangle removal

Random walks, totally unimodular matrices, and a randomised dual simplex algorithm

Randomized greedy matching. II

scholarly article by Jonathan Aronson et al published January 1995 in Random Structures and Algorithms

Randomly Coloring Constant Degree Graphs

Randomly coloring constant degree graphs

scholarly article by Martin Dyer et al published 3 August 2012 in Random Structures and Algorithms

Randomly coloring graphs with lower bounds on girth and maximum degree

scholarly article by Martin Dyer & Alan M. Frieze published 1 August 2003 in Random Structures and Algorithms

Randomly coloring random graphs

Randomly coloring simple hypergraphs

Randomly colouring graphs with lower bounds on girth and maximum degree

Randomly generated intersecting hypergraphs II

scholarly article by Tom Bohman et al published 2006 in Random Structures and Algorithms

Sampling from Log-Concave Distributions

Separating populations with wide data: A spectral analysis

Shortest path algorithms for knapsack type problems

scholarly article by A. M. Frieze published December 1976 in Mathematical Programming

Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010)

Splitting an Expander Graph

Stationary distribution and cover time of random walks on random digraphs

article by Colin Cooper & Alan M. Frieze published March 2012 in Journal of Combinatorial Theory, Series B

Survival time of a random graph

The Cover Time of Random Regular Graphs

The Game of JumbleG

The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems

The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence

The Strong Chromatic Index of Random Graphs

The cover time of random geometric graphs

The cover time of sparse random graphs

scholarly article by Colin Cooper & Alan M. Frieze published 2006 in Random Structures and Algorithms

The cover time of the giant component of a random graph

scholarly article by Colin Cooper & Alan M. Frieze published 2008 in Random Structures and Algorithms

The cover time of the preferential attachment graph

The cover times of random walks on random uniform hypergraphs

The emergence of a giant component in random subgraphs of pseudo-random graphs

scholarly article by Alan M. Frieze et al published 2003 in Random Structures and Algorithms

The game chromatic number of random graphs

scholarly article by Tom Bohman et al published 2008 in Random Structures and Algorithms

The height of randomk-trees and related branching processes

scholarly article by Colin Cooper et al published December 2014 in Random Structures and Algorithms

The probability of unique solutions of sequencing by hybridization

scientific article published in January 1994

The regularity lemma and approximation schemes for dense problems

The satisfiability threshold for randomly generated binary constraint satisfaction problems

article

The shortest-path problem for graphs with random arc-lengths

The t-Tone Chromatic Number of Random Graphs

The worst-case running time of the random simplex algorithm is exponential in the height

article by Andrei Z. Broder et al published October 1995 in Information Processing Letters

Tight Hamilton cycles in random uniform hypergraphs

scholarly article by Andrzej Dudek & Alan M. Frieze published 5 February 2012 in Random Structures and Algorithms

Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk

Variations on cops and robbers

Vertex Covers by Edge Disjoint Cliques

Walker-Breaker Games

When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

article by Alan M. Frieze et al published June 1995 in SIAM Journal on Computing