Alan M. Frieze
Orcid: 0000-0002-8481-5615Affiliations:
- Carnegie Mellon University, Pittsburgh, USA
According to our database1,
Alan M. Frieze
authored at least 390 papers
between 1974 and 2025.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on zbmath.org
-
on orcid.org
-
on id.loc.gov
-
on d-nb.info
-
on math.cmu.edu
-
on dl.acm.org
On csauthors.net:
Bibliography
2025
SIAM J. Discret. Math., 2025
Eur. J. Comb., 2025
2024
Random Struct. Algorithms, July, 2024
J. Graph Theory, April, 2024
Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\).
SIAM J. Discret. Math., March, 2024
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024
2023
J. Graph Theory, September, 2023
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
2022
SIAM J. Discret. Math., September, 2022
Random Struct. Algorithms, 2022
Math. Oper. Res., 2022
Giant descendant trees, matchings, and independent sets in age-biased attachment graphs.
J. Appl. Probab., 2022
Discret. Appl. Math., 2022
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
2021
SIAM J. Discret. Math., 2021
Random Struct. Algorithms, 2021
Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects.
Oper. Res. Lett., 2021
J. Comb. Theory B, 2021
Discret. Appl. Math., 2021
Electron. J. Comb., 2021
Proceedings of the Computing and Combinatorics - 27th International Conference, 2021
2020
Random Struct. Algorithms, July, 2020
Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis.
Random Struct. Algorithms, 2020
Electron. J. Comb., 2020
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
2019
Random Struct. Algorithms, 2019
How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?
J. Graph Theory, 2019
Discret. Appl. Math., 2019
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
Proceedings of the Approximation, 2019
2018
The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights.
SIAM J. Discret. Math., 2018
SIAM J. Discret. Math., 2018
J. Graph Theory, 2018
Comb. Probab. Comput., 2018
Electron. J. Comb., 2018
Proceedings of the 29th International Conference on Probabilistic, 2018
Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, 2018
2017
SIAM J. Discret. Math., 2017
Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity.
J. Comb. Theory B, 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
2016
SIAM J. Discret. Math., 2016
Random Struct. Algorithms, 2016
Electron. J. Comb., 2016
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
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
Electron. J. Comb., 2015
2014
On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three.
Random Struct. Algorithms, 2014
Random Struct. Algorithms, 2014
Cover time of a random graph with a degree sequence II: Allowing vertices of degree two.
Random Struct. Algorithms, 2014
2013
Theor. Comput. Sci., 2013
Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010).
SIAM J. Comput., 2013
Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013
2012
Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables.
Random Struct. Algorithms, 2012
Random Struct. Algorithms, 2012
J. Comb. Theory B, 2012
Electron. J. Comb., 2012
Proceedings of the Algorithms and Models for the Web Graph - 9th International Workshop, 2012
Proceedings of the Algorithms and Models for the Web Graph - 9th International Workshop, 2012
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012
Proceedings of the 9th Meeting on Analytic Algorithmics and Combinatorics, 2012
2011
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011
Comb. Probab. Comput., 2011
CoRR, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the Structural Information and Communication Complexity, 2011
2010
SIAM J. Discret. Math., 2010
SIAM J. Discret. Math., 2010
Finding a maximum matching in a sparse random graph in <i>O</i>(<i>n</i>) expected time.
J. ACM, 2010
CoRR, 2010
CoRR, 2010
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
Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables
CoRR, 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009
2008
Theor. Comput. Sci., 2008
Random Struct. Algorithms, 2008
Electron. J. Comb., 2008
Electron. J. Comb., 2008
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Proceedings of the Nano-Net - Third International ICST Conference, 2008
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008
2007
Comb. Probab. Comput., 2007
Comb. Probab. Comput., 2007
Proceedings of the Algorithms and Models for the Web-Graph, 5th International Workshop, 2007
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007
2006
Random Struct. Algorithms, 2006
Discret. Math. Theor. Comput. Sci., 2006
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
2005
Random Struct. Algorithms, 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
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005
2004
Random Struct. Algorithms, 2004
Random Struct. Algorithms, 2004
The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence.
Comb. Probab. Comput., 2004
Proceedings of the Algorithms and Models for the Web-Graph: Third International Workshop, 2004
Proceedings of the 45th Symposium on Foundations of Computer Science, 2004
Proceedings of the Approximation, 2004
2003
A probabilistic analysis of randomly generated binary constraint satisfaction problems.
Theor. Comput. Sci., 2003
Random Struct. Algorithms, 2003
Random Struct. Algorithms, 2003
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003
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
Proceedings of the Approximation, 2003
2002
Comb. Probab. Comput., 2002
Comb. Probab. Comput., 2002
Comb. Probab. Comput., 2002
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002
2001
The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
Proceedings of the Fifth Annual International Conference on Computational Biology, 2001
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
2000
Random Struct. Algorithms, 2000
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least <i>k</i>.
J. Graph Theory, 2000
On the Number of Perfect Matchings and Hamilton Cycles in e-Regular Non-bipartite Graphs.
Electron. J. Comb., 2000
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
1999
SIAM J. Discret. Math., 1999
Random Struct. Algorithms, 1999
Random Struct. Algorithms, 1999
Electron. J. Comb., 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
SIAM J. Comput., 1998
Random Struct. Algorithms, 1998
Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal.
Algorithmica, 1998
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998
Proceedings of the LATIN '98: Theoretical Informatics, 1998
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
1997
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
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
J. Algorithms, 1996
Comb. Probab. Comput., 1996
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996
Proceedings of the Integer Programming and Combinatorial Optimization, 1996
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
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
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
Proceedings of the Algorithms, 1996
1995
Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
Random Struct. Algorithms, 1995
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.
Inf. Process. Lett., 1995
Comb. Probab. Comput., 1995
Electron. J. Comb., 1995
Proceedings of the Integer Programming and Combinatorial Optimization, 1995
1994
J. Comput. Biol., 1994
Inf. Process. Lett., 1994
Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
Electron. Colloquium Comput. Complex., 1994
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994
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
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.
Comb. Probab. Comput., 1993
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993
1992
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
J. Comb. Theory B, 1992
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
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
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
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
1990
Random Struct. Algorithms, 1990
Math. Program., 1990
J. Comb. Theory B, 1990
Probabilistic Analysis of the Generalised Assignment Problem.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990
1989
Math. Program., 1989
Math. Oper. Res., 1989
J. Algorithms, 1989
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
1988
SIAM J. Comput., 1988
Math. Oper. Res., 1988
J. Algorithms, 1988
1987
On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients.
SIAM J. Comput., 1987
Inf. Process. Lett., 1987
1986
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
Discret. Appl. Math., 1985
Discret. Appl. Math., 1985
An Algorithm for Finding a Matroid Basis which Maximizes the Products of the Weights of the Elements.
BIT, 1985
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
1984
Inf. Process. Lett., 1984
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
1983
Discret. Math., 1983
Discret. Appl. Math., 1983
1982
On the worst-case performance of some algorithms for the asymmetric traveling salesman problem.
Networks, 1982
1980
Discret. Appl. Math., 1980
1979
1976
1974
Math. Program., 1974