dblp.uni-trier.dewww.uni-trier.de

Alan M. Frieze Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
239EEPrasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin: Average-Case Analyses of Vickrey Costs. APPROX-RANDOM 2009: 434-447
238EEAlan M. Frieze, Páll Melsted, Michael Mitzenmacher: An Analysis of Random-Walk Cuckoo Hashing. APPROX-RANDOM 2009: 490-503
237EEColin Cooper, Alan M. Frieze, Tomasz Radzik: Multiple Random Walks and Interacting Particle Systems. ICALP (2) 2009: 399-410
236EEAmin Coja-Oghlan, Colin Cooper, Alan M. Frieze: An efficient sparse regularity concept. SODA 2009: 207-216
235EEAmin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik: On smoothed k-CNF formulas and the Walksat algorithm. SODA 2009: 451-460
234EEColin Cooper, Alan M. Frieze: The cover time of random geometric graphs. SODA 2009: 48-57
233EEAlan M. Frieze, Páll Melsted: Randomly colouring simple hypergraphs CoRR abs/0901.3699: (2009)
232EEAlan M. Frieze, Páll Melsted: Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables CoRR abs/0910.5535: (2009)
231EEAlan M. Frieze, Jon M. Kleinberg, R. Ravi, Warren Debany: Line-of-Sight Networks. Combinatorics, Probability & Computing 18(1-2): 145-163 (2009)
230EEColin Cooper, Alan M. Frieze: Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401-439. Random Struct. Algorithms 34(2): 300-304 (2009)
2008
229EEAlan M. Frieze, Ravi Kannan: A new approach to the planted clique problem. FSTTCS 2008
228EEPrasad Chebolu, Alan M. Frieze, Páll Melsted: Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. ICALP (1) 2008: 161-172
227EEColin Cooper, Alan M. Frieze: Random Walks on Random Graphs. NanoNet 2008: 95-106
226EEAlan M. Frieze, Santosh Vempala, Juan Vera: Logconcave random graphs. STOC 2008: 779-788
225EETom Bohman, Alan M. Frieze, Benny Sudakov: The game chromatic number of random graphs. Random Struct. Algorithms 32(2): 223-235 (2008)
224EEColin Cooper, Alan M. Frieze: The cover time of the giant component of a random graph. Random Struct. Algorithms 32(4): 401-439 (2008)
223EEPrasad Chebolu, Alan M. Frieze: Hamilton Cycles in Random Lifts of Directed Graphs. SIAM J. Discrete Math. 22(2): 520-540 (2008)
222EEAndrew Beveridge, Tom Bohman, Alan M. Frieze, Oleg Pikhurko: Game chromatic index of graphs with given restrictions on degrees. Theor. Comput. Sci. 407(1-3): 242-249 (2008)
2007
221EEColin Cooper, Alan M. Frieze: The Cover Time of Random Digraphs. APPROX-RANDOM 2007: 422-435
220EEAvrim Blum, Amin Coja-Oghlan, Alan M. Frieze, Shuheng Zhou: Separating Populations with Wide Data: A Spectral Analysis. ISAAC 2007: 439-451
219EEAlan M. Frieze, Jon M. Kleinberg, R. Ravi, Warren Debany: Line-of-sight networks. SODA 2007: 968-977
218EEAbraham D. Flaxman, Alan M. Frieze, Juan Vera: A Geometric Preferential Attachment Model of Networks II. WAW 2007: 41-55
217EEColin Cooper, Alan M. Frieze, Gregory B. Sorkin: Random 2-SAT with Prescribed Literal Degrees. Algorithmica 48(3): 249-265 (2007)
216EEAbraham D. Flaxman, Alan M. Frieze, Juan Vera: Adversarial Deletion in a Scale-Free Random Graph Process. Combinatorics, Probability & Computing 16(2): 261-270 (2007)
215EETom Bohman, Alan M. Frieze, Tomasz Luczak, Oleg Pikhurko, Clifford D. Smyth, Joel Spencer, Oleg Verbitsky: First-Order Definability of Trees and Sparse Random Graphs. Combinatorics, Probability & Computing 16(3): 375-400 (2007)
214EEAbraham D. Flaxman, Alan M. Frieze, Juan Carlos Vera: On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem. Combinatorics, Probability & Computing 16(5): 713-732 (2007)
213EEAlan M. Frieze, Michael Krivelevich, Clifford D. Smyth: On the Chromatic Number of Random Graphs with a Fixed Degree Sequence. Combinatorics, Probability & Computing 16(5): 733-746 (2007)
212EEAlan M. Frieze, Ryan Martin, Julien Moncel, Miklós Ruszinkó, Clifford D. Smyth: Codes identifying sets of vertices in random networks. Discrete Mathematics 307(9-10): 1094-1107 (2007)
211 Abraham D. Flaxman, Alan M. Frieze, Juan Vera: A Geometric Preferential Attachment Model of Networks. Internet Mathematics 3(2): (2007)
210 Alan M. Frieze, Juan Vera, Soumen Chakrabarti: The Influence of Search Engines on Preferential Attachment. Internet Mathematics 3(3): (2007)
209EEColin Cooper, Alan M. Frieze: The cover time of the preferential attachment graph. J. Comb. Theory, Ser. B 97(2): 269-290 (2007)
208EEColin Cooper, Alan M. Frieze: The cover time of sparse random graphs. Random Struct. Algorithms 30(1-2): 1-16 (2007)
207EETom Bohman, Alan M. Frieze, Ryan Martin, Miklós Ruszinkó, Clifford D. Smyth: Randomly generated intersecting hypergraphs II. Random Struct. Algorithms 30(1-2): 17-34 (2007)
206EEAbraham D. Flaxman, Alan M. Frieze: The diameter of randomly perturbed digraphs and some applications. Random Struct. Algorithms 30(4): 484-504 (2007)
205EEAlan M. Frieze, Gregory B. Sorkin: The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. SIAM J. Comput. 36(5): 1435-1452 (2007)
2006
204EEAlan M. Frieze: Random graphs. SODA 2006: 960
203EEAlan M. Frieze, Juan Vera: On randomly colouring locally sparse graphs. Discrete Mathematics & Theoretical Computer Science 8(1): 121-128 (2006)
202EEK. Burgin, Prasad Chebolu, Colin Cooper, Alan M. Frieze: Hamilton cycles in random lifts of graphs. Eur. J. Comb. 27(8): 1282-1293 (2006)
201EEAbraham D. Flaxman, Alan M. Frieze, Michael Krivelevich: On the random 2-stage minimum spanning tree. Random Struct. Algorithms 28(1): 24-36 (2006)
200EEAlan M. Frieze, Michael Molloy: The satisfiability threshold for randomly generated binary constraint satisfaction problems. Random Struct. Algorithms 28(3): 323-339 (2006)
199EEAlan M. Frieze, Michael Krivelevich: Almost universal graphs. Random Struct. Algorithms 28(4): 499-510 (2006)
198EEMartin E. Dyer, Abraham D. Flaxman, Alan M. Frieze, Eric Vigoda: Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms 29(4): 450-465 (2006)
2005
197EEAbraham Flaxman, Alan M. Frieze, Juan Vera: Adversarial deletion in a scale free random graph process. SODA 2005: 287-292
196EESoumen Chakrabarti, Alan M. Frieze, Juan Vera: The influence of search engines on preferential attachment. SODA 2005: 293-300
195EEAbraham D. Flaxman, Alan M. Frieze, Michael Krivelevich: On the random 2-stage minimum spanning tree. SODA 2005: 919-926
194EEColin Cooper, Alan M. Frieze: The cover time of two classes of random graphs. SODA 2005: 961-970
193EEAbraham Flaxman, Alan M. Frieze, Juan Carlos Vera: On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. STOC 2005: 441-449
192EEAlan M. Frieze, Nicholas C. Wormald: Random k-Sat: A Tight Threshold For Moderately Growing k. Combinatorica 25(3): 297-305 (2005)
191 Abraham Flaxman, Alan M. Frieze, Trevor I. Fenner: High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. Internet Mathematics 2(1): (2005)
190EEAlan M. Frieze, Michael Krivelevich: On packing Hamilton cycles in ?-regular graphs. J. Comb. Theory, Ser. B 94(1): 159-172 (2005)
189EEAlan M. Frieze: Perfect matchings in random bipartite graphs with minimal degree at least 2. Random Struct. Algorithms 26(3): 319-358 (2005)
188EEColin Cooper, Alan M. Frieze: The Cover Time of Random Regular Graphs. SIAM J. Discrete Math. 18(4): 728-740 (2005)
187EEAlan M. Frieze, Michael Krivelevich, Benny Sudakov: The Strong Chromatic Index of Random Graphs. SIAM J. Discrete Math. 19(3): 719-727 (2005)
2004
186EEAbraham Flaxman, Alan M. Frieze: The Diameter of Randomly Perturbed Digraphs and Some Applications.. APPROX-RANDOM 2004: 345-356
185EEMartin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda: Randomly Coloring Constant Degree Graphs. FOCS 2004: 582-589
184EEAbraham Flaxman, Alan M. Frieze, Juan Vera: A Geometric Preferential Attachment Model of Networks. WAW 2004: 44-55
183 Geoffrey Atkinson, Alan M. Frieze: On the b-Independence Number of Sparse Random Graphs. Combinatorics, Probability & Computing 13(3): 295-309 (2004)
182 Colin Cooper, Alan M. Frieze: The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence. Combinatorics, Probability & Computing 13(3): 319-337 (2004)
181EEMartin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda: Randomly coloring constant degree graphs Electronic Colloquium on Computational Complexity (ECCC)(009): (2004)
180EEAlan M. Frieze, Ravi Kannan, Santosh Vempala: Fast monte-carlo algorithms for finding low-rank approximations. J. ACM 51(6): 1025-1041 (2004)
179EEAbraham Flaxman, Alan M. Frieze, Eli Upfal: Efficient communication in an ad-hoc network. J. Algorithms 52(1): 1-7 (2004)
178EEPetros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering Large Graphs via the Singular Value Decomposition. Machine Learning 56(1-3): 9-33 (2004)
177EEAlan M. Frieze: On Random Symmetric Travelling Salesman Problems. Math. Oper. Res. 29(4): 878-890 (2004)
176EEAlan M. Frieze, Michael Krivelevich, Ryan Martin: The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Struct. Algorithms 24(1): 42-50 (2004)
175EETom Bohman, Alan M. Frieze, Michael Krivelevich, Ryan Martin: Adding random edges to dense graphs. Random Struct. Algorithms 24(2): 105-117 (2004)
174EETom Bohman, Alan M. Frieze, Nicholas C. Wormald: Avoidance of a giant component in half the edge set of a random graph. Random Struct. Algorithms 25(4): 432-449 (2004)
2003
173EEAbraham Flaxman, Alan M. Frieze, Trevor I. Fenner: High Degree Vertices and Eigenvalues in the Preferential Attachment Graph. RANDOM-APPROX 2003: 264-274
172EEAlan M. Frieze, Michael Molloy: The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems. RANDOM-APPROX 2003: 275-289
171EEColin Cooper, Alan M. Frieze: The cover time of sparse random graphs. SODA 2003: 140-147
170EEAlan M. Frieze, Boris Pittel: Perfect matchings in random graphs with prescribed minimal degree. SODA 2003: 148-157
169EETom Bohman, Colin Cooper, Alan M. Frieze, Ryan Martin, Miklós Ruszinkó: On Randomly Generated Intersecting Hypergraphs. Electr. J. Comb. 10: (2003)
168 Colin Cooper, Alan M. Frieze: Crawling on Simple Models of Web Graphs. Internet Mathematics 1(1): (2003)
167 Colin Cooper, Alan M. Frieze, Juan Vera: Random Deletion in a Scale-Free Random Graph Process. Internet Mathematics 1(4): (2003)
166EETom Bohman, Alan M. Frieze, Ryan Martin: How many random edges make a dense graph hamiltonian? Random Struct. Algorithms 22(1): 33-42 (2003)
165EEColin Cooper, Alan M. Frieze: A general model of web graphs. Random Struct. Algorithms 22(3): 311-335 (2003)
164EEMartin E. Dyer, Alan M. Frieze: Randomly coloring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms 23(2): 167-179 (2003)
163EETom Bohman, Alan M. Frieze: Arc-Disjoint Paths in Expander Digraphs. SIAM J. Comput. 32(2): 326-344 (2003)
162 Martin E. Dyer, Alan M. Frieze, Michael Molloy: A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theor. Comput. Sci. 290(3): 1815-1828 (2003)
2002
161EEAlan M. Frieze: On Random Symmetric Travelling Salesman Problems. FOCS 2002: 789-798
160EEEleni Drinea, Alan M. Frieze, Michael Mitzenmacher: Balls and bins models with feedback. SODA 2002: 308-315
159EEColin Cooper, Alan M. Frieze, Gregory B. Sorkin: A note on random 2-SAT with prescribed literal degrees. SODA 2002: 316-320
158EEColin Cooper, Alan M. Frieze: Crawling on web graphs. STOC 2002: 419-427
157 Colin Cooper, Alan M. Frieze: Multi-Coloured Hamilton Cycles In Random Edge-Coloured Graphs. Combinatorics, Probability & Computing 11(2): (2002)
156 Colin Cooper, Alan M. Frieze, Bruce A. Reed: Random Regular Graphs Of Non-Constant Degree: Connectivity And Hamiltonicity. Combinatorics, Probability & Computing 11(3): (2002)
155 Colin Cooper, Alan M. Frieze, Bruce A. Reed, Oliver Riordan: Random Regular Graphs Of Non-Constant Degree: Independence And Chromatic Number. Combinatorics, Probability & Computing 11(4): (2002)
154EEAlan M. Frieze, Michael Krivelevich: Hamilton cycles in random subgraphs of pseudo-random graphs. Discrete Mathematics 256(1-2): 137-150 (2002)
153 Alan M. Frieze, Bjarni V. Halldórsson: Optimal Sequencing by Hybridization in Rounds. Journal of Computational Biology 9(2): 355-369 (2002)
152 Tom Bohman, Alan M. Frieze: Addendum to avoiding a giant component. Random Struct. Algorithms 20(1): 126-130 (2002)
151EEMartin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 31(5): 1527-1541 (2002)
2001
150EEColin Cooper, Alan M. Frieze: A General Model of Undirected Web Graphs. ESA 2001: 500-511
149 Tom Bohman, Alan M. Frieze: Arc-Disjoint Paths in Expander Digraphs. FOCS 2001: 558-567
148 Martin E. Dyer, Alan M. Frieze: Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. FOCS 2001: 579-587
147EEAlan M. Frieze, Bjarni V. Halldórsson: Optimal sequencing by hybridization in rounds. RECOMB 2001: 141-148
146EEAlan M. Frieze, Gregory B. Sorkin: The probabilistic relationship between the assignment and asymmetric traveling salesman problems. SODA 2001: 652-660
145EETom Bohman, Alan M. Frieze, Miklós Ruszinkó, Lubos Thoma: Vertex Covers by Edge Disjoint Cliques. Combinatorica 21(2): 171-197 (2001)
144 Tom Bohman, Alan M. Frieze, Miklós Ruszinkó, Lubos Thoma: G-Intersecting Families. Combinatorics, Probability & Computing 10(5): (2001)
143EEAndrei Z. Broder, Alan M. Frieze, Eli Upfal: A general approach to dynamic packet routing with bounded buffers. J. ACM 48(2): 324-349 (2001)
142 Colin Cooper, Martin E. Dyer, Alan M. Frieze: On Markov Chains for Randomly H-Coloring a Graph. J. Algorithms 39(1): 117-134 (2001)
141 Alan M. Frieze: Hamilton cycles in the union of random permutations. Random Struct. Algorithms 18(1): 83-94 (2001)
140 Tom Bohman, Alan M. Frieze: Avoiding a giant component. Random Struct. Algorithms 19(1): 75-85 (2001)
2000
139EEAlan M. Frieze: Edge-disjoint paths in expander graphs. SODA 2000: 717-725
138 Alan M. Frieze, Lei Zhao: Optimal Construction Of Edge-Disjoint Paths In Random Regular Graphs. Combinatorics, Probability & Computing 9(3): (2000)
137EEAlan M. Frieze, Miklós Ruszinkó, Lubos Thoma: A Note on Random Minimum Length Spanning Trees. Electr. J. Comb. 7: (2000)
136EETom Bohman, Colin Cooper, Alan M. Frieze: Min-Wise Independent Linear Permutations. Electr. J. Comb. 7: (2000)
135EETom Bohman, Alan M. Frieze, Miklós Ruszinkó, Lubos Thoma: Note on Sparse Random Graphs and Cover Graphs. Electr. J. Comb. 7: (2000)
134EEAlan M. Frieze: On the Number of Perfect Matchings and Hamilton Cycles in e-Regular Non-bipartite Graphs. Electr. J. Comb. 7: (2000)
133 Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher: Min-Wise Independent Permutations. J. Comput. Syst. Sci. 60(3): 630-659 (2000)
132 Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe: Average-case complexity of shortest-paths problems in the vertex-potential model. Random Struct. Algorithms 16(1): 33-46 (2000)
131 Colin Cooper, Alan M. Frieze: Hamilton cycles in random graphs and directed graphs. Random Struct. Algorithms 16(4): 369-401 (2000)
130EEAlan M. Frieze: Edge-Disjoint Paths in Expander Graphs. SIAM J. Comput. 30(6): 1790-1801 (2000)
1999
129EEMartin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. FOCS 1999: 210-217
128EEChristian Borgs, Jennifer T. Chayes, Alan M. Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van H. Vu: Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics. FOCS 1999: 218-229
127EEFranco P. Preparata, Alan M. Frieze, Eli Upfal: On the power of universal bases in sequencing by hybridization. RECOMB 1999: 295-301
126EEPetros Drineas, Alan M. Frieze, Ravi Kannan, Santosh Vempala, V. Vinay: Clustering in Large Graphs and Matrices. SODA 1999: 291-299
125EEAlan M. Frieze, Lei Zhao: Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs. SODA 1999: 346-355
124EEAlan M. Frieze, Ravi Kannan: Quick Approximation to Matrices and Applications. Combinatorica 19(2): 175-220 (1999)
123EEAlan M. Frieze, Ravi Kannan: A Simple Algorithm for Constructing Szemere'di's Regularity Partition. Electr. J. Comb. 6: (1999)
122 Alan M. Frieze, Michael Molloy: Splitting an Expander Graph. J. Algorithms 33(1): 166-172 (1999)
121 Alan M. Frieze, Franco P. Preparata, Eli Upfal: Optimal Reconstruction of a Sequence from its Probes. Journal of Computational Biology 6(3/4): (1999)
120 Andrei Z. Broder, Alan M. Frieze, Eli Upfal: Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach. Random Struct. Algorithms 14(1): 87-109 (1999)
119 Colin Cooper, Alan M. Frieze: Mixing properties of the Swendsen-Wang process on classes of graphs. Random Struct. Algorithms 15(3-4): 242-261 (1999)
118EEAlan M. Frieze, Michal Karonski, Lubos Thoma: On Perfect Matchings and Hamilton Cycles in Sums of Random Trees. SIAM J. Discrete Math. 12(2): 208-216 (1999)
1998
117EEAlan M. Frieze, Ravi Kannan, Santosh Vempala: Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. FOCS 1998: 370-378
116EEAndrei Z. Broder, Alan M. Frieze, Eli Upfal: Dynamic Packet Routing on Arrays with Bounded Buffers. LATIN 1998: 273-281
115EEAlan M. Frieze: Disjoint Paths in Expander Graphs via Random Walks: A Short Survey. RANDOM 1998: 1-14
114EERichard Cole, Alan M. Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh K. Sitaraman, Eli Upfal: On Balls and Bins with Deletions. RANDOM 1998: 145-158
113EEAndrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher: Min-Wise Independent Permutations (Extended Abstract). STOC 1998: 327-336
112 Alan M. Frieze, Wojciech Szpankowski: Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal. Algorithmica 21(1): 21-36 (1998)
111 Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. Algorithmica 22(1/2): 35-52 (1998)
110EEWenceslas Fernandez de la Vega, Alan M. Frieze, Miklos Santha: Average-Case Analysis of the Merging Algorithm of Hwang and Lin. Algorithmica 22(4): 483-489 (1998)
109EEAndrew Beveridge, Alan M. Frieze, Colin McDiarmid: Random Minimum Length Spanning Trees in Regular Graphs. Combinatorica 18(3): 311-333 (1998)
108 Jonathan Aronson, Alan M. Frieze, Boris Pittel: Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Struct. Algorithms 12(2): 111-177 (1998)
107EEMartin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM J. Comput. 27(5): 1262-1272 (1998)
106 Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal: Optimal Construction of Edge-Disjoint Paths in Random Graphs. SIAM J. Comput. 28(2): 541-573 (1998)
1997
105 Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe: Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model. RANDOM 1997: 15-26
104EEAndrei Z. Broder, Alan M. Frieze, Eli Upfal: Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). STOC 1997: 531-539
103 Alan M. Frieze, Mark Jerrum: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18(1): 67-81 (1997)
102 Alan M. Frieze, Colin McDiarmid: Algorithmic theory of random graphs. Random Struct. Algorithms 10(1-2): 5-42 (1997)
1996
101EEAlan M. Frieze, Wojciech Szpankowski: Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal. ESA 1996: 194-207
100 Alan M. Frieze, Ravi Kannan: The Regularity Lemma and Approximation Schemes for Dense Problems. FOCS 1996: 12-20
99 Sanjeev Arora, Alan M. Frieze, Haim Kaplan: A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems. FOCS 1996: 21-30
98 Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh Vempala: A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. FOCS 1996: 330-338
97 Alan M. Frieze, Mark Jerrum, Ravi Kannan: Learning Linear Transformations. FOCS 1996: 359-368
96 Andrei Z. Broder, Alan M. Frieze, Eli Upfal: A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract). FOCS 1996: 390-399
95EEHui Chen, Alan M. Frieze: Coloring Bipartite Hypergraphs. IPCO 1996: 345-358
94 Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal: An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs. SODA 1996: 261-268
93 Colin Cooper, Alan M. Frieze, Michael Molloy, Bruce A. Reed: Perfect Matchings in Random r-regular, s-uniform Hypergraphs. Combinatorics, Probability & Computing 5: 1-14 (1996)
92 Béla Bollobás, Trevor I. Fenner, Alan M. Frieze: On the Best Case of Heapsort. J. Algorithms 20(2): 205-217 (1996)
91 Alan M. Frieze, Stephen Suen: Analysis of Two Simple Heuristics on a Random Instance of k-SAT. J. Algorithms 20(2): 312-355 (1996)
90 Alan M. Frieze, Mark Jerrum, Michael Molloy, Robert W. Robinson, Nicholas C. Wormald: Generating and Counting Hamilton Cycles in Random Regular Graphs. J. Algorithms 21(1): 176-198 (1996)
89 Hui Chen, Alan M. Frieze: Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph. Random Struct. Algorithms 9(4): 359-377 (1996)
1995
88EEAlan M. Frieze, Mark Jerrum: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. IPCO 1995: 1-13
87 Alan M. Frieze, Mark Jerrum: An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. Combinatorica 15(1): 67-83 (1995)
86 Alan M. Frieze, Bruce A. Reed: Covering the Edges of a Random Graph by Cliques. Combinatorica 15(4): 489-497 (1995)
85 Colin Cooper, Alan M. Frieze: On the Connectivity of Random k-th Nearest Neighbour Graphs. Combinatorics, Probability & Computing 4: 343-362 (1995)
84 Alan M. Frieze, A. J. Radcliffe, Stephen Suen: Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs. Combinatorics, Probability & Computing 4: 47-66 (1995)
83EEMichael H. Albert, Alan M. Frieze, Bruce A. Reed: Multicoloured Hamilton Cycles. Electr. J. Comb. 2: (1995)
82EEColin Cooper, Alan M. Frieze: Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold. Electr. J. Comb. 2: (1995)
81EEAndrei Z. Broder, Alan M. Frieze, Carsten Lund, Steven Phillips, Nick Reingold: Balanced Allocations for Tree-Like Inputs. Inf. Process. Lett. 55(6): 329-332 (1995)
80EEAndrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, Eli Upfal: The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height. Inf. Process. Lett. 56(2): 79-81 (1995)
79 Martin E. Dyer, Trevor I. Fenner, Alan M. Frieze, Andrew Thomason: On Key Storage in Secure Networks. J. Cryptology 8(4): 189-200 (1995)
78 Martin E. Dyer, Alan M. Frieze, Stephen Suen: Ordering Clone Libraries in Computational Biology. Journal of Computational Biology 2(2): 207-218 (1995)
77 Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen: Randomized Greedy Matching II. Random Struct. Algorithms 6(1): 55-74 (1995)
76 Noga Alon, Alan M. Frieze, Dominic Welsh: Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case. Random Struct. Algorithms 6(4): 459-478 (1995)
75 Alan M. Frieze, Svante Janson: Perfect Matchings in Random s-Uniform Hypergraphs. Random Struct. Algorithms 7(1): 41-58 (1995)
74 Alan M. Frieze, Richard M. Karp, Bruce A. Reed: When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? SIAM J. Comput. 24(3): 484-493 (1995)
1994
73 Noga Alon, Alan M. Frieze, Dominic Welsh: Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs FOCS 1994: 24-35
72 Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen: On the Greedy Heuristic for Matchings. SODA 1994: 141-149
71 Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Cycles in Dense Graphs. SODA 1994: 336-343
70 Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal: Optimal Construction of Edge-Disjoint Paths in Random Graphs. SODA 1994: 603-612
69 Colin Cooper, Alan M. Frieze, Michael Molloy: Hamilton Cycles in Random Regular Digraphs. Combinatorics, Probability & Computing 3: 39-49 (1994)
68 Alan M. Frieze, Shang-Hua Teng: On the Complexity of Computing the Diameter of a Polytope. Computational Complexity 4: 207-219 (1994)
67EEAlan M. Frieze, Michael Molloy: Broadcasting in Random Graphs. Discrete Applied Mathematics 54(1): 77-79 (1994)
66EENoga Alon, Alan M. Frieze, Dominic Welsh: Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case Electronic Colloquium on Computational Complexity (ECCC) 1(5): (1994)
65 Yossi Azar, Andrei Z. Broder, Alan M. Frieze: On the Problem of Approximating the Number of Bases of a Matroid. Inf. Process. Lett. 50(1): 9-11 (1994)
64EEColin Cooper, Alan M. Frieze: Hamilton Cycles in a Class of Random Directed Graphs. J. Comb. Theory, Ser. B 62(1): 151-163 (1994)
63 Martin E. Dyer, Alan M. Frieze: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64: 1-16 (1994)
62 Alan M. Frieze, Svante Janson, Tomasz Luczak: Introduction. Random Struct. Algorithms 5(1): 1-3 (1994)
61 Alan M. Frieze, Brendan D. McKay: Multicolored Trees in Random Graphs. Random Struct. Algorithms 5(1): 45-56 (1994)
60 Andrei Z. Broder, Alan M. Frieze, Eli Shamir: Finding Hidden Hamiltonian Cycles. Random Struct. Algorithms 5(3): 395-411 (1994)
59 Andrei Z. Broder, Alan M. Frieze, Eli Shamir, Eli Upfal: Near-perfect Token Distribution. Random Struct. Algorithms 5(4): 559-572 (1994)
58 Alan M. Frieze, Stephen Suen: On the Independence Number of Random Cubic Graphs. Random Struct. Algorithms 5(5): 649-664 (1994)
57 Andrei Z. Broder, Alan M. Frieze, Eli Upfal: Existence and Construction of Edge-Disjoint Paths on Expander Graphs. SIAM J. Comput. 23(5): 976-989 (1994)
1993
56 Andrei Z. Broder, Alan M. Frieze, Eli Upfal: On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas. SODA 1993: 322-330
55 Alan M. Frieze, A. J. Radcliffe, Stephen Suen: Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs. SODA 1993: 341-351
54 Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani: A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Combinatorics, Probability & Computing 2: 271-284 (1993)
53EEAlan M. Frieze, Bruce A. Reed: Polychromatic Hamilton cycles. Discrete Mathematics 118(1-3): 69-74 (1993)
1992
52EEAndrei Z. Broder, Alan M. Frieze, Eli Shamir, Eli Upfal: Near-perfect Token Distribution. ICALP 1992: 308-317
51 Alan M. Frieze, Richard M. Karp, Bruce A. Reed: When is the Assignment Bound Tight for the Asymmetric Traveling Salesman Problem? IPCO 1992: 453-461
50 Martin E. Dyer, Alan M. Frieze: Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm. IPCO 1992: 72-84
49EEAlan M. Frieze, Gary L. Miller, Shang-Hua Teng: Separator Based Parallel Divide and Conquer in Computational Geometry. SPAA 1992: 420-429
48 Andrei Z. Broder, Alan M. Frieze, Eli Upfal: Existence and Construction of Edge Disjoint Paths on Expander Graphs STOC 1992: 140-149
47 Neil J. Calkin, Alan M. Frieze, Brendan D. McKay: On Subgraph Sizes in Random Graphs. Combinatorics, Probability & Computing 1: 123-134 (1992)
46EEAlan M. Frieze, Tomasz Luczak: On the independence and chromatic numbers of random regular graphs. J. Comb. Theory, Ser. B 54(1): 123-132 (1992)
45 Martin E. Dyer, Alan M. Frieze: Probabilistic analysis of the generalised assignment problem. Math. Program. 55: 169-181 (1992)
44 Neil J. Calkin, Alan M. Frieze, Ludek Kucera: On the Expected Performance of a Parallel Algorithm for Finding Maximal Independent Subsets of a Random Graph. Random Struct. Algorithms 3(2): 215-222 (1992)
43 Alan M. Frieze, Stephen Suen: Counting the Number of Hamilton Cycles in Random Digraphs. Random Struct. Algorithms 3(3): 235-242 (1992)
1991
42 Andrei Z. Broder, Alan M. Frieze, Eli Shamir: Finding Hidden Hamiltonian Cycles (Extended Abstract) STOC 1991: 182-189
41EEMichael H. Albert, Alan M. Frieze: Occupancy problems and random algebras. Discrete Mathematics 87(1): 1-8 (1991)
40EEMartin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. J. ACM 38(1): 1-17 (1991)
39 Martin E. Dyer, Alan M. Frieze: Randomized Greedy Matching. Random Struct. Algorithms 2(1): 29-46 (1991)
38 Béla Bollobás, Alan M. Frieze: Spanning Maximal Planar Subgraphs of Random Graphs. Random Struct. Algorithms 2(2): 225-232 (1991)
37 Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph. Random Struct. Algorithms 2(2): 233-240 (1991)
1990
36 Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of the Generalised Assignment Problem. IPCO 1990: 189-200
35EEMartin E. Dyer, Alan M. Frieze: On an optimization problem with nested constraints. Discrete Applied Mathematics 26(2-3): 159-173 (1990)
34EEAlan M. Frieze: On the independence number of random graphs. Discrete Mathematics 81(2): 171-175 (1990)
33EEColin Cooper, Alan M. Frieze: The limiting probability that alpha-in, ß-out is strongly connected. J. Comb. Theory, Ser. B 48(1): 117-134 (1990)
32 Martin E. Dyer, Alan M. Frieze: On Patching Algorithms for Random Asymmetric Travelling Salesman Problems. Math. Program. 46: 361-378 (1990)
31 Neil J. Calkin, Alan M. Frieze: Probabilistic Analysis of a Parallel Algorithm for Finding Maximal Independent Sets. Random Struct. Algorithms 1(1): 39-50 (1990)
30 Alan M. Frieze, Colin McDiarmid, Bruce A. Reed: Greedy Matching on the Line. SIAM J. Comput. 19(4): 666-672 (1990)
1989
29 Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies STOC 1989: 375-381
28 Alan M. Frieze: Survival time of a random graph. Combinatorica 9(2): 133-143 (1989)
27 Alan M. Frieze, Colin J. H. McDiarmid: On random minimum lenght spanning trees. Combinatorica 9(4): 363-374 (1989)
26 Martin E. Dyer, Alan M. Frieze: The Solution of Some Random NP-Hard Problems in Polynomial Expected Time. J. Algorithms 10(4): 451-489 (1989)
25 Alan M. Frieze, J. Yadegar, S. El-Horbaty, D. Parkinson: Algorithms for assignment problems on an array processor. Parallel Computing 11(2): 151-162 (1989)
1988
24EEAlan M. Frieze: Partitioning random graphs into large cycles. Discrete Mathematics 70(2): 149-158 (1988)
23 Alan M. Frieze: On the Random Construction of Heaps. Inf. Process. Lett. 27(2): 103-109 (1988)
22 Alan M. Frieze: An Algorithm for Finding Hamilton Cycles in Random Directed Graphs. J. Algorithms 9(2): 181-204 (1988)
21EEAlan M. Frieze: Finding hamilton cycles in sparse random graphs. J. Comb. Theory, Ser. B 44(2): 230-250 (1988)
20EEAlan M. Frieze, B. Jackson, Colin J. H. McDiarmid, Bruce A. Reed: Edge-colouring random graphs. J. Comb. Theory, Ser. B 45(2): 135-149 (1988)
19 Alan M. Frieze, Johan Håstad, Ravi Kannan, J. C. Lagarias, Adi Shamir: Reconstructing Truncated Integer Variables Satisfying Linear Congruences. SIAM J. Comput. 17(2): 262-280 (1988)
18 Martin E. Dyer, Alan M. Frieze: On the Complexity of Computing the Volume of a Polyhedron. SIAM J. Comput. 17(5): 967-974 (1988)
1987
17 Alan M. Frieze, B. Jackson: Large holes in sparse random graphs. Combinatorica 7(3): 265-274 (1987)
16 Béla Bollobás, Trevor I. Fenner, Alan M. Frieze: An algorithm for finding Hamilton cycles in a random graph. Combinatorica 7(4): 327-341 (1987)
15 Alan M. Frieze: Parallel Algorithms for Finding Hamilton Cycles in Random Graphs. Inf. Process. Lett. 25(2): 111-117 (1987)
14EEAlan M. Frieze, B. Jackson: Large induced trees in sparse random graphs. J. Comb. Theory, Ser. B 42(2): 181-195 (1987)
13 Alan M. Frieze: On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients. SIAM J. Comput. 16(6): 1052-1072 (1987)
1986
12 Martin E. Dyer, Alan M. Frieze: Fast Solution of Some Random NP-Hard Problems FOCS 1986: 331-336
11EEAlan M. Frieze: On large matchings and cycles in sparse random graphs. Discrete Mathematics 59(3): 243-256 (1986)
10 Martin E. Dyer, Alan M. Frieze: Planar 3DM is NP-Complete. J. Algorithms 7(2): 174-184 (1986)
9EEAlan M. Frieze: Maximum matchings in a class of random graphs. J. Comb. Theory, Ser. B 40(2): 196-212 (1986)
8 Alan M. Frieze: On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem. SIAM J. Comput. 15(2): 536-539 (1986)
1985
7 Béla Bollobás, Trevor I. Fenner, Alan M. Frieze: An Algorithm for Finding Hamilton Cycles in a Random Graph STOC 1985: 430-439
6 Trevor I. Fenner, Alan M. Frieze: An Algorithm for Finding a Matroid Basis which Maximizes the Products of the Weights of the Elements. BIT 25(3): 434-438 (1985)
1984
5 Alan M. Frieze, Ravi Kannan, J. C. Lagarias: Linear Congruential Generators Do Not Produce Random Sequences FOCS 1984: 480-484
4 Martin E. Dyer, Alan M. Frieze: A Partitioning Algorithm for Minimum Weighted Euclidean Matching. Inf. Process. Lett. 18(2): 59-62 (1984)
3EETrevor I. Fenner, Alan M. Frieze: Hamiltonian cycles in random regular graphs. J. Comb. Theory, Ser. B 37(2): 103-112 (1984)
1983
2EETrevor I. Fenner, Alan M. Frieze: On the existence of Hamiltonian cycles in a class of random graphs. Discrete Mathematics 45(2-3): 301-305 (1983)
1982
1 Trevor I. Fenner, Alan M. Frieze: On the connectivity of random m-orientable graphs and digraphs. Combinatorica 2(4): 347-359 (1982)

Coauthor Index

1Michael H. Albert [41] [83]
2Noga Alon [66] [73] [76]
3Jonathan Aronson [72] [77] [108]
4Sanjeev Arora [99]
5Geoffrey Atkinson [183]
6Yossi Azar [65]
7Andrew Beveridge [109] [222]
8Avrim Blum [98] [111] [220]
9Tom Bohman [135] [136] [140] [144] [145] [149] [152] [163] [166] [169] [174] [175] [207] [215] [222] [225]
10Béla Bollobás [7] [16] [38] [92]
11Christian Borgs [128]
12Andrei Z. Broder [42] [48] [52] [56] [57] [59] [60] [65] [70] [80] [81] [94] [96] [104] [106] [113] [116] [120] [133] [143]
13K. Burgin [202]
14Neil J. Calkin [31] [44] [47]
15Soumen Chakrabarti [196] [210]
16Moses Charikar [113] [133]
17Jennifer T. Chayes [128]
18Prasad Chebolu [202] [223] [228] [239]
19Hui Chen [89] [95]
20Amin Coja-Oghlan [220] [235] [236]
21Richard Cole [114]
22Colin Cooper [33] [64] [69] [82] [85] [93] [105] [119] [131] [132] [136] [142] [150] [155] [156] [157] [158] [159] [165] [167] [168] [169] [171] [182] [188] [194] [202] [208] [209] [217] [221] [224] [227] [230] [234] [236] [237]
23Warren Debany [219] [231]
24Eleni Drinea [160]
25Petros Drineas [126] [178]
26Martin E. Dyer [4] [10] [12] [18] [26] [29] [32] [35] [36] [37] [39] [40] [45] [50] [54] [63] [71] [72] [77] [78] [79] [80] [107] [129] [142] [148] [151] [162] [164] [181] [185] [198]
27S. El-Horbaty [25]
28Uriel Feige [235]
29Trevor I. Fenner [1] [2] [3] [6] [7] [16] [79] [92] [173] [191]
30Abraham D. Flaxman (Abraham Flaxman) [173] [179] [184] [186] [191] [193] [195] [197] [198] [201] [206] [211] [214] [216] [218]
31Bjarni V. Halldórsson [147] [153]
32Johan Håstad [19]
33Thomas P. Hayes [181] [185]
34B. Jackson [14] [17] [20]
35Svante Janson [62] [75]
36Mark Jerrum [71] [87] [88] [90] [97] [103] [107] [129] [151]
37Ravi Kannan (Ravindran Kannan) [5] [19] [29] [40] [54] [97] [98] [100] [111] [117] [123] [124] [126] [178] [180] [229]
38Haim Kaplan [99]
39Ajai Kapoor [54]
40Michal Karonski [118]
41Richard M. Karp [51] [74]
42Jeong Han Kim [128]
43Jon M. Kleinberg [219] [231]
44Michael Krivelevich [154] [175] [176] [187] [190] [195] [199] [201] [213] [235]
45Ludek Kucera [44]
46Jeffrey C. Lagarias (J. C. Lagarias) [5] [19]
47Tomasz Luczak [46] [62] [215]
48Carsten Lund [81]
49Bruce M. Maggs [114]
50Ryan Martin [166] [169] [175] [176] [207] [212]
51Colin McDiarmid (Colin J. H. McDiarmid) [20] [27] [30] [102] [109]
52Brendan D. McKay [47] [61]
53Kurt Mehlhorn [105] [132]
54Páll Melsted [228] [232] [233] [238] [239]
55Gary L. Miller [49]
56Michael Mitzenmacher [113] [114] [133] [160] [238]
57Michael Molloy (Michael S. O. Molloy) [67] [69] [90] [93] [122] [162] [172] [200]
58Julien Moncel [212]
59D. Parkinson [25]
60Ljubomir Perkovic [54]
61Steven Phillips [81]
62Oleg Pikhurko [215] [222]
63Boris Pittel [108] [170]
64Franco P. Preparata [121] [127]
65Volker Priebe [105] [132]
66A. J. Radcliffe [55] [84]
67Tomasz Radzik [237]
68Prabhakar Raghavan [80]
69R. Ravi [219] [231]
70Bruce A. Reed [20] [30] [51] [53] [74] [83] [86] [93] [155] [156]
71Nick Reingold [81]
72Andréa W. Richa [114]
73Oliver Riordan [155]
74Robert W. Robinson [90]
75Miklós Ruszinkó [135] [137] [144] [145] [169] [207] [212]
76Miklos Santha [110]
77Adi Shamir [19]
78Eli Shamir [42] [52] [59] [60]
79Ramesh K. Sitaraman [114]
80Clifford D. Smyth [207] [212] [213] [215]
81Gregory B. Sorkin [146] [159] [205] [217] [239]
82Joel H. Spencer (Joel Spencer) [215]
83Benny Sudakov [187] [225]
84Stephen Suen [43] [55] [58] [70] [72] [77] [78] [84] [91] [94] [106]
85Wojciech Szpankowski [101] [112]
86Shang-Hua Teng [49] [68]
87Prasad Tetali [128]
88Lubos Thoma [118] [135] [137] [144] [145]
89Andrew Thomason [79]
90Eli Upfal [48] [52] [56] [57] [59] [70] [80] [94] [96] [104] [106] [114] [116] [120] [121] [127] [143] [179]
91Umesh V. Vazirani [54]
92Wenceslas Fernandez de la Vega [110]
93Santosh Vempala [98] [111] [117] [126] [178] [180] [226]
94Juan Vera [167] [184] [196] [197] [203] [210] [211] [216] [218] [226]
95Juan Carlos Vera [193] [214]
96Oleg Verbitsky [215]
97Eric Vigoda [128] [181] [185] [198]
98Dan Vilenchik [235]
99V. Vinay [126] [178]
100Van H. Vu [128]
101Dominic Welsh [66] [73] [76]
102Nicholas C. Wormald [90] [174] [192]
103J. Yadegar [25]
104Lei Zhao [125] [138]
105Shuheng Zhou [220]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)