| 2009 |
|---|
| 234 | EE | Amin Coja-Oghlan,
Colin Cooper,
Alan M. Frieze:
An efficient sparse regularity concept.
SODA 2009: 207-216 |
| 233 | EE | Amin Coja-Oghlan,
Uriel Feige,
Alan M. Frieze,
Michael Krivelevich,
Dan Vilenchik:
On smoothed k-CNF formulas and the Walksat algorithm.
SODA 2009: 451-460 |
| 232 | EE | Colin Cooper,
Alan M. Frieze:
The cover time of random geometric graphs.
SODA 2009: 48-57 |
| 231 | EE | Alan M. Frieze,
Páll Melsted:
Randomly colouring simple hypergraphs
CoRR abs/0901.3699: (2009) |
| 230 | EE | Alan M. Frieze,
Jon M. Kleinberg,
R. Ravi,
Warren Debany:
Line-of-Sight Networks.
Combinatorics, Probability & Computing 18(1-2): 145-163 (2009) |
| 229 | EE | Colin 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 |
|---|
| 228 | EE | Alan M. Frieze,
Ravi Kannan:
A new approach to the planted clique problem.
FSTTCS 2008 |
| 227 | EE | Prasad 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 |
| 226 | EE | Alan M. Frieze,
Santosh Vempala,
Juan Vera:
Logconcave random graphs.
STOC 2008: 779-788 |
| 225 | EE | Tom Bohman,
Alan M. Frieze,
Benny Sudakov:
The game chromatic number of random graphs.
Random Struct. Algorithms 32(2): 223-235 (2008) |
| 224 | EE | Colin Cooper,
Alan M. Frieze:
The cover time of the giant component of a random graph.
Random Struct. Algorithms 32(4): 401-439 (2008) |
| 223 | EE | Prasad Chebolu,
Alan M. Frieze:
Hamilton Cycles in Random Lifts of Directed Graphs.
SIAM J. Discrete Math. 22(2): 520-540 (2008) |
| 222 | EE | Andrew 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 |
|---|
| 221 | EE | Colin Cooper,
Alan M. Frieze:
The Cover Time of Random Digraphs.
APPROX-RANDOM 2007: 422-435 |
| 220 | EE | Avrim Blum,
Amin Coja-Oghlan,
Alan M. Frieze,
Shuheng Zhou:
Separating Populations with Wide Data: A Spectral Analysis.
ISAAC 2007: 439-451 |
| 219 | EE | Alan M. Frieze,
Jon M. Kleinberg,
R. Ravi,
Warren Debany:
Line-of-sight networks.
SODA 2007: 968-977 |
| 218 | EE | Abraham D. Flaxman,
Alan M. Frieze,
Juan Vera:
A Geometric Preferential Attachment Model of Networks II.
WAW 2007: 41-55 |
| 217 | EE | Colin Cooper,
Alan M. Frieze,
Gregory B. Sorkin:
Random 2-SAT with Prescribed Literal Degrees.
Algorithmica 48(3): 249-265 (2007) |
| 216 | EE | Abraham D. Flaxman,
Alan M. Frieze,
Juan Vera:
Adversarial Deletion in a Scale-Free Random Graph Process.
Combinatorics, Probability & Computing 16(2): 261-270 (2007) |
| 215 | EE | Tom 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) |
| 214 | EE | Abraham 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) |
| 213 | EE | Alan M. Frieze,
Michael Krivelevich,
Cliff Smyth:
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence.
Combinatorics, Probability & Computing 16(5): 733-746 (2007) |
| 212 | EE | Alan 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) |
| 209 | EE | Colin Cooper,
Alan M. Frieze:
The cover time of the preferential attachment graph.
J. Comb. Theory, Ser. B 97(2): 269-290 (2007) |
| 208 | EE | Colin Cooper,
Alan M. Frieze:
The cover time of sparse random graphs.
Random Struct. Algorithms 30(1-2): 1-16 (2007) |
| 207 | EE | Tom 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) |
| 206 | EE | Abraham D. Flaxman,
Alan M. Frieze:
The diameter of randomly perturbed digraphs and some applications.
Random Struct. Algorithms 30(4): 484-504 (2007) |
| 205 | EE | Alan 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 |
|---|
| 204 | EE | Alan M. Frieze:
Random graphs.
SODA 2006: 960 |
| 203 | EE | Alan M. Frieze,
Juan Vera:
On randomly colouring locally sparse graphs.
Discrete Mathematics & Theoretical Computer Science 8(1): 121-128 (2006) |
| 202 | EE | K. Burgin,
Prasad Chebolu,
Colin Cooper,
Alan M. Frieze:
Hamilton cycles in random lifts of graphs.
Eur. J. Comb. 27(8): 1282-1293 (2006) |
| 201 | EE | Abraham D. Flaxman,
Alan M. Frieze,
Michael Krivelevich:
On the random 2-stage minimum spanning tree.
Random Struct. Algorithms 28(1): 24-36 (2006) |
| 200 | EE | Alan M. Frieze,
Michael Molloy:
The satisfiability threshold for randomly generated binary constraint satisfaction problems.
Random Struct. Algorithms 28(3): 323-339 (2006) |
| 199 | EE | Alan M. Frieze,
Michael Krivelevich:
Almost universal graphs.
Random Struct. Algorithms 28(4): 499-510 (2006) |
| 198 | EE | Martin 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 |
|---|
| 197 | EE | Abraham Flaxman,
Alan M. Frieze,
Juan Vera:
Adversarial deletion in a scale free random graph process.
SODA 2005: 287-292 |
| 196 | EE | Soumen Chakrabarti,
Alan M. Frieze,
Juan Vera:
The influence of search engines on preferential attachment.
SODA 2005: 293-300 |
| 195 | EE | Abraham D. Flaxman,
Alan M. Frieze,
Michael Krivelevich:
On the random 2-stage minimum spanning tree.
SODA 2005: 919-926 |
| 194 | EE | Colin Cooper,
Alan M. Frieze:
The cover time of two classes of random graphs.
SODA 2005: 961-970 |
| 193 | EE | Abraham 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 |
| 192 | EE | Alan 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) |
| 190 | EE | Alan M. Frieze,
Michael Krivelevich:
On packing Hamilton cycles in ?-regular graphs.
J. Comb. Theory, Ser. B 94(1): 159-172 (2005) |
| 189 | EE | Alan M. Frieze:
Perfect matchings in random bipartite graphs with minimal degree at least 2.
Random Struct. Algorithms 26(3): 319-358 (2005) |
| 188 | EE | Colin Cooper,
Alan M. Frieze:
The Cover Time of Random Regular Graphs.
SIAM J. Discrete Math. 18(4): 728-740 (2005) |
| 187 | EE | Alan M. Frieze,
Michael Krivelevich,
Benny Sudakov:
The Strong Chromatic Index of Random Graphs.
SIAM J. Discrete Math. 19(3): 719-727 (2005) |
| 2004 |
|---|
| 186 | EE | Abraham Flaxman,
Alan M. Frieze:
The Diameter of Randomly Perturbed Digraphs and Some Applications..
APPROX-RANDOM 2004: 345-356 |
| 185 | EE | Martin E. Dyer,
Alan M. Frieze,
Thomas P. Hayes,
Eric Vigoda:
Randomly Coloring Constant Degree Graphs.
FOCS 2004: 582-589 |
| 184 | EE | Abraham 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) |
| 181 | EE | Martin E. Dyer,
Alan M. Frieze,
Thomas P. Hayes,
Eric Vigoda:
Randomly coloring constant degree graphs
Electronic Colloquium on Computational Complexity (ECCC)(009): (2004) |
| 180 | EE | Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
Fast monte-carlo algorithms for finding low-rank approximations.
J. ACM 51(6): 1025-1041 (2004) |
| 179 | EE | Abraham Flaxman,
Alan M. Frieze,
Eli Upfal:
Efficient communication in an ad-hoc network.
J. Algorithms 52(1): 1-7 (2004) |
| 178 | EE | Petros 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) |
| 177 | EE | Alan M. Frieze:
On Random Symmetric Travelling Salesman Problems.
Math. Oper. Res. 29(4): 878-890 (2004) |
| 176 | EE | Alan 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) |
| 175 | EE | Tom Bohman,
Alan M. Frieze,
Michael Krivelevich,
Ryan Martin:
Adding random edges to dense graphs.
Random Struct. Algorithms 24(2): 105-117 (2004) |
| 174 | EE | Tom 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 |
|---|
| 173 | EE | Abraham Flaxman,
Alan M. Frieze,
Trevor I. Fenner:
High Degree Vertices and Eigenvalues in the Preferential Attachment Graph.
RANDOM-APPROX 2003: 264-274 |
| 172 | EE | Alan M. Frieze,
Michael Molloy:
The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems.
RANDOM-APPROX 2003: 275-289 |
| 171 | EE | Colin Cooper,
Alan M. Frieze:
The cover time of sparse random graphs.
SODA 2003: 140-147 |
| 170 | EE | Alan M. Frieze,
Boris Pittel:
Perfect matchings in random graphs with prescribed minimal degree.
SODA 2003: 148-157 |
| 169 | EE | Tom 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) |
| 166 | EE | Tom Bohman,
Alan M. Frieze,
Ryan Martin:
How many random edges make a dense graph hamiltonian?
Random Struct. Algorithms 22(1): 33-42 (2003) |
| 165 | EE | Colin Cooper,
Alan M. Frieze:
A general model of web graphs.
Random Struct. Algorithms 22(3): 311-335 (2003) |
| 164 | EE | Martin E. Dyer,
Alan M. Frieze:
Randomly coloring graphs with lower bounds on girth and maximum degree.
Random Struct. Algorithms 23(2): 167-179 (2003) |
| 163 | EE | Tom 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 |
|---|
| 161 | EE | Alan M. Frieze:
On Random Symmetric Travelling Salesman Problems.
FOCS 2002: 789-798 |
| 160 | EE | Eleni Drinea,
Alan M. Frieze,
Michael Mitzenmacher:
Balls and bins models with feedback.
SODA 2002: 308-315 |
| 159 | EE | Colin Cooper,
Alan M. Frieze,
Gregory B. Sorkin:
A note on random 2-SAT with prescribed literal degrees.
SODA 2002: 316-320 |
| 158 | EE | Colin 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) |
| 154 | EE | Alan 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) |
| 151 | EE | Martin E. Dyer,
Alan M. Frieze,
Mark Jerrum:
On Counting Independent Sets in Sparse Graphs.
SIAM J. Comput. 31(5): 1527-1541 (2002) |
| 2001 |
|---|
| 150 | EE | Colin 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 |
| 147 | EE | Alan M. Frieze,
Bjarni V. Halldórsson:
Optimal sequencing by hybridization in rounds.
RECOMB 2001: 141-148 |
| 146 | EE | Alan M. Frieze,
Gregory B. Sorkin:
The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
SODA 2001: 652-660 |
| 145 | EE | Tom 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) |
| 143 | EE | Andrei 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 |
|---|
| 139 | EE | Alan 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) |
| 137 | EE | Alan M. Frieze,
Miklós Ruszinkó,
Lubos Thoma:
A Note on Random Minimum Length Spanning Trees.
Electr. J. Comb. 7: (2000) |
| 136 | EE | Tom Bohman,
Colin Cooper,
Alan M. Frieze:
Min-Wise Independent Linear Permutations.
Electr. J. Comb. 7: (2000) |
| 135 | EE | Tom Bohman,
Alan M. Frieze,
Miklós Ruszinkó,
Lubos Thoma:
Note on Sparse Random Graphs and Cover Graphs.
Electr. J. Comb. 7: (2000) |
| 134 | EE | Alan 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) |
| 130 | EE | Alan M. Frieze:
Edge-Disjoint Paths in Expander Graphs.
SIAM J. Comput. 30(6): 1790-1801 (2000) |
| 1999 |
|---|
| 129 | EE | Martin E. Dyer,
Alan M. Frieze,
Mark Jerrum:
On Counting Independent Sets in Sparse Graphs.
FOCS 1999: 210-217 |
| 128 | EE | Christian 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 |
| 127 | EE | Franco P. Preparata,
Alan M. Frieze,
Eli Upfal:
On the power of universal bases in sequencing by hybridization.
RECOMB 1999: 295-301 |
| 126 | EE | Petros Drineas,
Alan M. Frieze,
Ravi Kannan,
Santosh Vempala,
V. Vinay:
Clustering in Large Graphs and Matrices.
SODA 1999: 291-299 |
| 125 | EE | Alan M. Frieze,
Lei Zhao:
Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs.
SODA 1999: 346-355 |
| 124 | EE | Alan M. Frieze,
Ravi Kannan:
Quick Approximation to Matrices and Applications.
Combinatorica 19(2): 175-220 (1999) |
| 123 | EE | Alan 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) |
| 118 | EE | Alan 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 |
|---|
| 117 | EE | Alan M. Frieze,
Ravi Kannan,
Santosh Vempala:
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations.
FOCS 1998: 370-378 |
| 116 | EE | Andrei Z. Broder,
Alan M. Frieze,
Eli Upfal:
Dynamic Packet Routing on Arrays with Bounded Buffers.
LATIN 1998: 273-281 |
| 115 | EE | Alan M. Frieze:
Disjoint Paths in Expander Graphs via Random Walks: A Short Survey.
RANDOM 1998: 1-14 |
| 114 | EE | Richard 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 |
| 113 | EE | Andrei 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) |
| 110 | EE | Wenceslas 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) |
| 109 | EE | Andrew 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) |
| 107 | EE | Martin 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 |
| 104 | EE | Andrei 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 |
|---|
| 101 | | Alan 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 |
| 95 | | Hui 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 |
|---|
| 88 | | Alan 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) |
| 83 | EE | Michael H. Albert,
Alan M. Frieze,
Bruce A. Reed:
Multicoloured Hamilton Cycles.
Electr. J. Comb. 2: (1995) |
| 82 | EE | Colin Cooper,
Alan M. Frieze:
Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold.
Electr. J. Comb. 2: (1995) |
| 81 | EE | Andrei 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) |
| 80 | EE | Andrei 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) |
| 67 | EE | Alan M. Frieze,
Michael Molloy:
Broadcasting in Random Graphs.
Discrete Applied Mathematics 54(1): 77-79 (1994) |
| 66 | EE | Noga 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) |
| 64 | EE | Colin 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) |
| 53 | EE | Alan M. Frieze,
Bruce A. Reed:
Polychromatic Hamilton cycles.
Discrete Mathematics 118(1-3): 69-74 (1993) |
| 1992 |
|---|
| 52 | | Andrei 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 |
| 49 | EE | Alan 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) |
| 46 | EE | Alan 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 |
| 41 | EE | Michael H. Albert,
Alan M. Frieze:
Occupancy problems and random algebras.
Discrete Mathematics 87(1): 1-8 (1991) |
| 40 | EE | Martin 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 |
| 35 | EE | Martin E. Dyer,
Alan M. Frieze:
On an optimization problem with nested constraints.
Discrete Applied Mathematics 26(2-3): 159-173 (1990) |
| 34 | EE | Alan M. Frieze:
On the independence number of random graphs.
Discrete Mathematics 81(2): 171-175 (1990) |
| 33 | EE | Colin 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 |
|---|
| 24 | EE | Alan 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) |
| 21 | EE | Alan M. Frieze:
Finding hamilton cycles in sparse random graphs.
J. Comb. Theory, Ser. B 44(2): 230-250 (1988) |
| 20 | EE | Alan 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) |
| 14 | EE | Alan 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 |
| 11 | EE | Alan 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) |
| 9 | EE | Alan 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) |
| 3 | EE | Trevor I. Fenner,
Alan M. Frieze:
Hamiltonian cycles in random regular graphs.
J. Comb. Theory, Ser. B 37(2): 103-112 (1984) |
| 1983 |
|---|
| 2 | EE | Trevor 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) |
