2024
Rainbow Hamilton cycles in random geometric graphs.
Random Struct. Algorithms, July, 2024
Rainbow powers of a Hamilton cycle in <i>G<sub>n,p</sub></i>.
J. Graph Theory, April, 2024
On the Concentration of the Maximum Degree in the Duplication-Divergence Models.
SIAM J. Discret. Math., March, 2024
Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\).
SIAM J. Discret. Math., March, 2024
On the Chromatic Number of Random Regular Hypergraphs.
SIAM J. Discret. Math., 2024
SIAM J. Discret. Math., 2024
The Bright Side of Simple Heuristics for the TSP.
Electron. J. Comb., 2024
On the Intersecting Family Process.
Electron. J. Comb., 2024
O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold.
Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024
2023
Spanners in randomly weighted graphs: Euclidean case.
J. Graph Theory, September, 2023
Colorful Hamilton Cycles in Random Graphs.
SIAM J. Discret. Math., March, 2023
Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds.
CoRR, 2023
Multitrees in Random Graphs.
Electron. J. Comb., 2023
Subexponential mixing for partition chains on grid-like graphs.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
2022
Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs.
SIAM J. Discret. Math., September, 2022
On the Cover Time of the Emerging Giant.
SIAM J. Discret. Math., 2022
A scaling limit for the length of the longest cycle in a sparse random digraph.
Random Struct. Algorithms, 2022
A Randomly Weighted Minimum Arborescence with a Random Cost Constraint.
Math. Oper. Res., 2022
Giant descendant trees, matchings, and independent sets in age-biased attachment graphs.
J. Appl. Probab., 2022
Spanners in randomly weighted graphs: Independent edge lengths.
Discret. Appl. Math., 2022
Localization game for random graphs.
Discret. Appl. Math., 2022
Rainbow spanning trees in randomly coloured G<sub>k-out</sub>.
CoRR, 2022
Learning from a Sample in Online Algorithms.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
2021
The Effect of Adding Randomly Weighted Edges.
SIAM J. Discret. Math., 2021
Hamiltonicity of Random Graphs in the Stochastic Block Model.
SIAM J. Discret. Math., 2021
Finding maximum matchings in random regular graphs in linear expected time.
Random Struct. Algorithms, 2021
Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects.
Oper. Res. Lett., 2021
Maker Breaker on digraphs.
J. Graph Theory, 2021
A scaling limit for the length of the longest cycle in a sparse random graph.
J. Comb. Theory B, 2021
Isomorphism for random <i>k</i>-uniform hypergraphs.
Inf. Process. Lett., 2021
Shortest paths with a cost constraint: A probabilistic analysis.
Discret. Appl. Math., 2021
A Randomly Weighted Minimum Spanning Tree with a Random Cost Constraint.
Electron. J. Comb., 2021
Minimum-Weight Combinatorial Structures Under Random Cost-Constraints.
Electron. J. Comb., 2021
2020
On the connectivity of proper colorings of random graphs and hypergraphs.
Random Struct. Algorithms, July, 2020
Random Graphs with a Fixed Maximum Degree.
SIAM J. Discret. Math., 2020
Hamilton cycles in random graphs with minimum degree at least 3: An improved analysis.
Random Struct. Algorithms, 2020
On random multi-dimensional assignment problems.
Discret. Appl. Math., 2020
On the Existence of Hamilton Cycles with a Periodic Pattern in a Random Digraph.
Electron. J. Comb., 2020
Degree Distribution for Duplication-Divergence Graphs: Large Deviations.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020
2019
A Random Variant of the Game of Plates and Olives.
SIAM J. Discret. Math., 2019
On the Cover Time of Dense Graphs.
SIAM J. Discret. Math., 2019
Pattern Colored Hamilton Cycles in Random Graphs.
SIAM J. Discret. Math., 2019
Perfect matchings and Hamiltonian cycles in the preferential attachment model.
Random Struct. Algorithms, 2019
Traveling in randomly embedded random graphs.
Random Struct. Algorithms, 2019
On the insertion time of random walk cuckoo hashing.
Random Struct. Algorithms, 2019
Notes on growing a tree in a graph.
Random Struct. Algorithms, 2019
Minors of a random binary matroid.
Random Struct. Algorithms, 2019
How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?
J. Graph Theory, 2019
A note on the localization number of random graphs: Diameter two case.
Discret. Appl. Math., 2019
A Note on Log-Concave Random Graphs.
Electron. J. Comb., 2019
On the Rank of a Random Binary Matrix.
Electron. J. Comb., 2019
On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs.
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
Elegantly Colored Paths and Cycles in Edge Colored Random Graphs.
SIAM J. Discret. Math., 2018
Discordant Voting Processes on Finite Graphs.
SIAM J. Discret. Math., 2018
A note on dispersing particles on a line.
Random Struct. Algorithms, 2018
Online purchasing under uncertainty.
Random Struct. Algorithms, 2018
A greedy algorithm for finding a large 2-matching on a random cubic graph.
J. Graph Theory, 2018
Balanced allocation through random walk.
Inf. Process. Lett., 2018
On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph.
Comb. Probab. Comput., 2018
Packing Hamilton Cycles Online.
Comb. Probab. Comput., 2018
On Rainbow Hamilton Cycles in Random Hypergraphs.
Electron. J. Comb., 2018
Constraining the Clustering Transition for Colorings of Sparse Random Graphs.
Electron. J. Comb., 2018
The Cover Time of a Biased Random Walk on a Random Cubic Graph.
Proceedings of the 29th International Conference on Probabilistic, 2018
The cover time of a biased random walk on <i>G<sub>n, p</sub></i>.
Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, 2018
2017
Minimum Cost Matching in a Random Graph with Random Costs.
SIAM J. Discret. Math., 2017
Separating subadditive euclidean functionals.
Random Struct. Algorithms, 2017
On random <i>k</i>-out subgraphs of large graphs.
Random Struct. Algorithms, 2017
Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity.
J. Comb. Theory B, 2017
Randomly coloring simple hypergraphs with fewer colors.
Inf. Process. Lett., 2017
The covertime of a biased random walk on G<sub>n, p</sub>.
CoRR, 2017
2016
Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk.
SIAM J. Discret. Math., 2016
Rainbow matchings and Hamilton cycles in random graphs.
Random Struct. Algorithms, 2016
Rainbow Arborescence in Random Digraphs.
J. Graph Theory, 2016
On the Length of a Random Minimum Spanning Tree.
Comb. Probab. Comput., 2016
Scalefree hardness of average-case Euclidean TSP approximation.
CoRR, 2016
Weak and Strong Versions of the 1-2-3 Conjecture for Uniform Hypergraphs.
Electron. J. Comb., 2016
2015
SIAM J. Discret. Math., 2015
Rainbow Connection of Random Regular Graphs.
SIAM J. Discret. Math., 2015
Efficient algorithms for three-dimensional axial and planar random assignment problems.
Random Struct. Algorithms, 2015
An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three.
Random Struct. Algorithms, 2015
On the chromatic number of a random hypergraph.
J. Comb. Theory B, 2015
Long Paths in Random Apollonian Networks.
Internet Math., 2015
Loose Hamilton Cycles in Regular Hypergraphs.
Comb. Probab. Comput., 2015
Between 2- and 3-Colorability.
Electron. J. Comb., 2015
On-line List Colouring of Random Graphs.
Electron. J. Comb., 2015
Power of k Choices and Rainbow Spanning Trees in Random Graphs.
Electron. J. Comb., 2015
2014
Expanders via Random Spanning Trees.
SIAM J. Comput., 2014
Analyzing Walksat on Random Formulas.
SIAM J. Comput., 2014
Rainbow hamilton cycles in random graphs.
Random Struct. Algorithms, 2014
On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three.
Random Struct. Algorithms, 2014
The height of random <i>k</i>-trees and related branching processes.
Random Struct. Algorithms, 2014
Cover time of a random graph with a degree sequence II: Allowing vertices of degree two.
Random Struct. Algorithms, 2014
Maker-breaker games on random geometric graphs.
Random Struct. Algorithms, 2014
Some Properties of Random Apollonian Networks.
Internet Math., 2014
Some Typical Properties of the Spatial Preferred Attachment Model.
Internet Math., 2014
The t-Tone Chromatic Number of Random Graphs.
Graphs Comb., 2014
Looking for vertex number one.
CoRR, 2014
The Topology of Competitively Constructed Graphs.
Electron. J. Comb., 2014
Packing Tree Factors in Random and Pseudo-random Graphs.
Electron. J. Comb., 2014
2013
The cover times of random walks on random uniform hypergraphs.
Theor. Comput. Sci., 2013
On the Game Chromatic Number of Sparse Random Graphs.
SIAM J. Discret. Math., 2013
Special Section on the Forty-Second Annual ACM Symposium on Theory of Computing (STOC 2010).
SIAM J. Comput., 2013
Tight Hamilton cycles in random uniform hypergraphs.
Random Struct. Algorithms, 2013
Component structure of the vacant set induced by a random walk on a random graph.
Random Struct. Algorithms, 2013
Coloring simple hypergraphs.
J. Comb. Theory B, 2013
Approximate counting of regular hypergraphs.
Inf. Process. Lett., 2013
Special Issue on Algorithms and Models for the Web Graph.
Internet Math., 2013
On the Non-Planarity of a Random Subgraph.
Comb. Probab. Comput., 2013
Algorithmic techniques for modeling and mining large graphs (AMAzING).
Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013
2012
Packing Tight Hamilton Cycles in Uniform Hypergraphs.
SIAM J. Discret. Math., 2012
Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables.
Random Struct. Algorithms, 2012
Packing tight Hamilton cycles in 3-uniform hypergraphs.
Random Struct. Algorithms, 2012
Packing hamilton cycles in random and pseudo-random hypergraphs.
Random Struct. Algorithms, 2012
Variations on cops and robbers.
J. Graph Theory, 2012
Stationary distribution and cover time of random walks on random digraphs.
J. Comb. Theory B, 2012
Cover time of a random graph with given degree sequence.
Discret. Math., 2012
Cops and Robbers on Geometric Graphs.
Comb. Probab. Comput., 2012
Rainbow Connection of Sparse Random Graphs.
Electron. J. Comb., 2012
Optimal Divisibility Conditions for Loose Hamilton Cycles in Random Hypergraphs.
Electron. J. Comb., 2012
Rainbow Hamilton Cycles in Uniform Hypergraphs.
Electron. J. Comb., 2012
On Certain Properties of Random Apollonian Networks.
Proceedings of the Algorithms and Models for the Web Graph - 9th International Workshop, 2012
Rainbow Connectivity of Sparse Random Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012
2011
An Analysis of Random-Walk Cuckoo Hashing.
SIAM J. Comput., 2011
The cover time of random geometric graphs.
Random Struct. Algorithms, 2011
Ramsey games with giants.
Random Struct. Algorithms, 2011
Randomly coloring simple hypergraphs.
Inf. Process. Lett., 2011
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011
Karp-Sipser on Random Graphs with a Fixed Degree Sequence.
Comb. Probab. Comput., 2011
Random greedy triangle-packing beyond the 7/4 barrier
CoRR, 2011
High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks
CoRR, 2011
Loose Hamilton Cycles in Random Uniform Hypergraphs.
Electron. J. Comb., 2011
The Cover Times of Random Walks on Hypergraphs.
Proceedings of the Structural Information and Communication Complexity, 2011
2010
Hamilton Cycles in Random Graphs with a Fixed Degree Sequence.
SIAM J. Discret. Math., 2010
Random Walks with Look-Ahead in Scale-Free Random Graphs.
SIAM J. Discret. Math., 2010
An Efficient Sparse Regularity Concept.
SIAM J. Discret. Math., 2010
SIAM J. Discret. Math., 2010
Randomly coloring random graphs.
Random Struct. Algorithms, 2010
Coloring H-free hypergraphs.
Random Struct. Algorithms, 2010
Anti-Ramsey properties of random graphs.
J. Comb. Theory B, 2010
Finding a maximum matching in a sparse random graph in <i>O</i>(<i>n</i>) expected time.
J. ACM, 2010
Average-case performance of heuristics for three-dimensional assignment problems
CoRR, 2010
Component structure induced by a random walk on a random graph
CoRR, 2010
Average case performance of heuristics for multi-dimensional assignment problems
CoRR, 2010
A note on the random greedy triangle-packing algorithm
CoRR, 2010
Logconcave Random Graphs.
Electron. J. Comb., 2010
Loose Hamilton Cycles in Random 3-Uniform Hypergraphs.
Electron. J. Comb., 2010
Hypergraphs with independent neighborhoods.
Comb., 2010
2009
Multiple Random Walks in Random Regular Graphs.
SIAM J. Discret. Math., 2009
Memoryless Rules for Achlioptas Processes.
SIAM J. Discret. Math., 2009
Corrigendum: The cover time of the giant component of a random graph, Random Structures and Algorithms 32 (2008), 401-439.
Random Struct. Algorithms, 2009
Hamilton cycles in 3-out.
Random Struct. Algorithms, 2009
Comb. Probab. Comput., 2009
Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hashtables
CoRR, 2009
Randomly colouring simple hypergraphs
CoRR, 2009
On smoothed <i>k</i>-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Multiple Random Walks and Interacting Particle Systems.
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009
Average-Case Analyses of Vickrey Costs.
Proceedings of the Approximation, 2009
2008
Game chromatic index of graphs with given restrictions on degrees.
Theor. Comput. Sci., 2008
Hamilton Cycles in Random Lifts of Directed Graphs.
SIAM J. Discret. Math., 2008
The cover time of the giant component of a random graph.
Random Struct. Algorithms, 2008
The game chromatic number of random graphs.
Random Struct. Algorithms, 2008
On the Chromatic Number of Simple Triangle-Free Triple Systems.
Electron. J. Comb., 2008
On Rainbow Trees and Cycles.
Electron. J. Comb., 2008
Random k-SAT: The Limiting Probability for Satisfiability for Moderately Growing k.
Electron. J. Comb., 2008
Random Walks on Random Graphs.
Proceedings of the Nano-Net - Third International ICST Conference, 2008
Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008
A new approach to the planted clique problem.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008
2007
The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems.
SIAM J. Comput., 2007
The diameter of randomly perturbed digraphs and some applications.
Random Struct. Algorithms, 2007
The cover time of sparse random graphs.
Random Struct. Algorithms, 2007
Randomly generated intersecting hypergraphs II.
Random Struct. Algorithms, 2007
The cover time of the preferential attachment graph.
J. Comb. Theory B, 2007
The Influence of Search Engines on Preferential Attachment.
Internet Math., 2007
A Geometric Preferential Attachment Model of Networks II.
Internet Math., 2007
A Geometric Preferential Attachment Model of Networks.
Internet Math., 2007
Codes identifying sets of vertices in random networks.
Discret. Math., 2007
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence.
Comb. Probab. Comput., 2007
On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem.
Comb. Probab. Comput., 2007
Adversarial Deletion in a Scale-Free Random Graph Process.
Comb. Probab. Comput., 2007
First-Order Definability of Trees and Sparse Random Graphs.
Comb. Probab. Comput., 2007
Random 2-SAT with Prescribed Literal Degrees.
Algorithmica, 2007
Separating Populations with Wide Data: A Spectral Analysis.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007
The Cover Time of Random Digraphs.
Proceedings of the Approximation, 2007
2006
The satisfiability threshold for randomly generated binary constraint satisfaction problems.
Random Struct. Algorithms, 2006
Random Struct. Algorithms, 2006
On the random 2-stage minimum spanning tree.
Random Struct. Algorithms, 2006
Randomly coloring sparse random graphs with fewer colors than the maximum degree.
Random Struct. Algorithms, 2006
Hamilton cycles in random lifts of graphs.
Eur. J. Comb., 2006
On randomly colouring locally sparse graphs.
Discret. Math. Theor. Comput. Sci., 2006
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006
2005
The Strong Chromatic Index of Random Graphs.
SIAM J. Discret. Math., 2005
The Cover Time of Random Regular Graphs.
SIAM J. Discret. Math., 2005
Perfect matchings in random bipartite graphs with minimal degree at least 2.
Random Struct. Algorithms, 2005
On packing Hamilton cycles in ?-regular graphs.
J. Comb. Theory B, 2005
High Degree Vertices and Eigenvalues in the Preferential Attachment Graph.
Internet Math., 2005
Random <i>k</i>-Sat: A Tight Threshold For Moderately Growing <i>k</i>.
Comb., 2005
The cover time of two classes of random graphs.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005
Identifying codes in random networks.
Proceedings of the 2005 IEEE International Symposium on Information Theory, 2005
2004
The emergence of a giant component in random subgraphs of pseudo-random graphs.
Random Struct. Algorithms, 2004
Avoidance of a giant component in half the edge set of a random graph.
Random Struct. Algorithms, 2004
Adding random edges to dense graphs.
Random Struct. Algorithms, 2004
On Random Symmetric Travelling Salesman Problems.
Math. Oper. Res., 2004
Clustering Large Graphs via the Singular Value Decomposition.
Mach. Learn., 2004
Efficient communication in an ad-hoc network.
J. Algorithms, 2004
Fast monte-carlo algorithms for finding low-rank approximations.
J. ACM, 2004
Randomly coloring constant degree graphs
Electron. Colloquium Comput. Complex., 2004
The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence.
Comb. Probab. Comput., 2004
On the b-Independence Number of Sparse Random Graphs.
Comb. Probab. Comput., 2004
2003
A probabilistic analysis of randomly generated binary constraint satisfaction problems.
Theor. Comput. Sci., 2003
Arc-Disjoint Paths in Expander Digraphs.
SIAM J. Comput., 2003
Randomly coloring graphs with lower bounds on girth and maximum degree.
Random Struct. Algorithms, 2003
A general model of web graphs.
Random Struct. Algorithms, 2003
How many random edges make a dense graph hamiltonian?
Random Struct. Algorithms, 2003
Random Deletion in a Scale-Free Random Graph Process.
Internet Math., 2003
Crawling on Simple Models of Web Graphs.
Internet Math., 2003
On Randomly Generated Intersecting Hypergraphs.
Electron. J. Comb., 2003
Perfect matchings in random graphs with prescribed minimal degree.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003
Proceedings of the Handbook of Graph Theory., 2003
2002
On Counting Independent Sets in Sparse Graphs.
SIAM J. Comput., 2002
Addendum to avoiding a giant component.
Random Struct. Algorithms, 2002
A new rounding procedure for the assignment problem with applications to dense graph arrangement problems.
Math. Program., 2002
On graph irregularity strength.
J. Graph Theory, 2002
Optimal Sequencing by Hybridization in Rounds.
J. Comput. Biol., 2002
Hamilton cycles in random subgraphs of pseudo-random graphs.
Discret. Math., 2002
Random Regular Graphs Of Non-Constant Degree: Independence And Chromatic Number.
Comb. Probab. Comput., 2002
Random Regular Graphs Of Non-Constant Degree: Connectivity And Hamiltonicity.
Comb. Probab. Comput., 2002
Multi-Coloured Hamilton Cycles In Random Edge-Coloured Graphs.
Comb. Probab. Comput., 2002
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Balls and bins models with feedback.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
A note on random 2-SAT with prescribed literal degrees.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
2001
Hamilton cycles in the union of random permutations.
Random Struct. Algorithms, 2001
Avoiding a giant component.
Random Struct. Algorithms, 2001
On Markov Chains for Randomly H-Coloring a Graph.
J. Algorithms, 2001
A general approach to dynamic packet routing with bounded buffers.
J. ACM, 2001
Comb. Probab. Comput., 2001
Vertex Covers by Edge Disjoint Cliques.
Comb., 2001
Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
A General Model of Undirected Web Graphs.
Proceedings of the Algorithms, 2001
2000
Edge-Disjoint Paths in Expander Graphs.
SIAM J. Comput., 2000
Average-case complexity of shortest-paths problems in the vertex-potential model.
Random Struct. Algorithms, 2000
Hamilton cycles in random graphs and directed graphs.
Random Struct. Algorithms, 2000
Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at least <i>k</i>.
J. Graph Theory, 2000
Min-Wise Independent Permutations.
J. Comput. Syst. Sci., 2000
Optimal Construction Of Edge-Disjoint Paths In Random Regular Graphs.
Comb. Probab. Comput., 2000
A Note on Random Minimum Length Spanning Trees.
Electron. J. Comb., 2000
On the Number of Perfect Matchings and Hamilton Cycles in e-Regular Non-bipartite Graphs.
Electron. J. Comb., 2000
Note on Sparse Random Graphs and Cover Graphs.
Electron. J. Comb., 2000
Min-Wise Independent Linear Permutations.
Electron. J. Comb., 2000
1999
On Perfect Matchings and Hamilton Cycles in Sums of Random Trees.
SIAM J. Discret. Math., 1999
Mixing properties of the Swendsen-Wang process on classes of graphs.
Random Struct. Algorithms, 1999
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach.
Random Struct. Algorithms, 1999
Optimal Reconstruction of a Sequence from its Probes.
J. Comput. Biol., 1999
Splitting an Expander Graph.
J. Algorithms, 1999
A Simple Algorithm for Constructing Szemere'di's Regularity Partition.
Electron. J. Comb., 1999
Quick Approximation to Matrices and Applications.
Comb., 1999
Clustering in Large Graphs and Matrices.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
On the power of universal bases in sequencing by hybridization.
Proceedings of the Third Annual International Conference on Research in Computational Molecular Biology, 1999
Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
Approximately Counting Hamilton Paths and Cycles in Dense Graphs.
SIAM J. Comput., 1998
Optimal Construction of Edge-Disjoint Paths in Random Graphs.
SIAM J. Comput., 1998
Maximum matchings in sparse random graphs: Karp-Sipser revisited.
Random Struct. Algorithms, 1998
Random Minimum Length Spanning Trees in Regular Graphs.
Comb., 1998
Average-Case Analysis of the Merging Algorithm of Hwang and Lin.
Algorithmica, 1998
Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal.
Algorithmica, 1998
A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.
Algorithmica, 1998
Min-Wise Independent Permutations (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Disjoint Paths in Expander Graphs via Random Walks: A Short Survey.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998
On Balls and Bins with Deletions.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998
Dynamic Packet Routing on Arrays with Bounded Buffers.
Proceedings of the LATIN '98: Theoretical Informatics, 1998
1997
Algorithmic theory of random graphs.
Random Struct. Algorithms, 1997
Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION.
Algorithmica, 1997
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
1996
Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph.
Random Struct. Algorithms, 1996
Analysis of Two Simple Heuristics on a Random Instance of k-SAT.
J. Algorithms, 1996
Generating and Counting Hamilton Cycles in Random Regular Graphs.
J. Algorithms, 1996
On the Best Case of Heapsort.
J. Algorithms, 1996
Perfect Matchings in Random r-regular, s-uniform Hypergraphs.
Comb. Probab. Comput., 1996
An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996
Coloring Bipartite Hypergraphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996
The Regularity Lemma and Approximation Schemes for Dense Problems.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
Learning Linear Transformations.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract).
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996
Greedy Algorithms for the Shortest Common Superstring that are Asmtotically Optimal.
Proceedings of the Algorithms, 1996
1995
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
SIAM J. Comput., 1995
Perfect Matchings in Random s-Uniform Hypergraphs.
Random Struct. Algorithms, 1995
Randomized Greedy Matching II.
Random Struct. Algorithms, 1995
Polynomial Time Randomized Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case.
Random Struct. Algorithms, 1995
On Key Storage in Secure Networks.
J. Cryptol., 1995
Ordering Clone Libraries in Computational Biology.
J. Comput. Biol., 1995
Balanced Allocations for Tree-Like Inputs.
Inf. Process. Lett., 1995
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.
Inf. Process. Lett., 1995
Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs.
Comb. Probab. Comput., 1995
On the Connectivity of Random k-th Nearest Neighbour Graphs.
Comb. Probab. Comput., 1995
Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold.
Electron. J. Comb., 1995
Multicoloured Hamilton Cycles.
Electron. J. Comb., 1995
Covering the Edges of a Random Graph by Cliques.
Comb., 1995
An Analysis of a Monte Carlo Algorithm for Estimating the Permanent.
Comb., 1995
Improved Approximation Algorithms for MAX <i>k</i>-CUT and MAX BISECTION.
Proceedings of the Integer Programming and Combinatorial Optimization, 1995
1994
Existence and Construction of Edge-Disjoint Paths on Expander Graphs.
SIAM J. Comput., 1994
On the Independence Number of Random Cubic Graphs.
Random Struct. Algorithms, 1994
Multicolored Trees in Random Graphs.
Random Struct. Algorithms, 1994
Random Struct. Algorithms, 1994
Near-perfect Token Distribution.
Random Struct. Algorithms, 1994
Finding Hidden Hamiltonian Cycles.
Random Struct. Algorithms, 1994
Random walks, totally unimodular matrices, and a randomised dual simplex algorithm.
Math. Program., 1994
Hamilton Cycles in a Class of Random Directed Graphs.
J. Comb. Theory B, 1994
The Probability of Unique Solutions of Sequencing by Hybridization.
J. Comput. Biol., 1994
On the Problem of Approximating the Number of Bases of a Matroid.
Inf. Process. Lett., 1994
Polynomial Time Randomised Approximation Schemes for Tutte-Gröthendieck Invariants: The Dense Case
Electron. Colloquium Comput. Complex., 1994
Broadcasting in Random Graphs.
Discret. Appl. Math., 1994
Hamilton Cycles in Random Regular Digraphs.
Comb. Probab. Comput., 1994
On the Complexity of Computing the Diameter of a Polytope.
Comput. Complex., 1994
Approximately Counting Hamilton Cycles in Dense Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994
On the Greedy Heuristic for Matchings.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994
Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
1993
Polychromatic Hamilton cycles.
Discret. Math., 1993
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.
Comb. Probab. Comput., 1993
On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993
1992
Counting the Number of Hamilton Cycles in Random Digraphs.
Random Struct. Algorithms, 1992
On the Expected Performance of a Parallel Algorithm for Finding Maximal Independent Subsets of a Random Graph.
Random Struct. Algorithms, 1992
Probabilistic analysis of the generalised assignment problem.
Math. Program., 1992
On the independence and chromatic numbers of random regular graphs.
J. Comb. Theory B, 1992
On Subgraph Sizes in Random Graphs.
Comb. Probab. Comput., 1992
Separator Based Parallel Divide and Conquer in Computational Geometry.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992
1991
Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph.
Random Struct. Algorithms, 1991
Randomized Greedy Matching.
Random Struct. Algorithms, 1991
Spanning Maximal Planar Subgraphs of Random Graphs.
Random Struct. Algorithms, 1991
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.
J. ACM, 1991
Occupancy problems and random algebras.
Discret. Math., 1991
Finding Hidden Hamiltonian Cycles (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
1990
Greedy Matching on the Line.
SIAM J. Comput., 1990
Probabilistic Analysis of a Parallel Algorithm for Finding Maximal Independent Sets.
Random Struct. Algorithms, 1990
On Patching Algorithms for Random Asymmetric Travelling Salesman Problems.
Math. Program., 1990
The limiting probability that alpha-in, ß-out is strongly connected.
J. Comb. Theory B, 1990
On the independence number of random graphs.
Discret. Math., 1990
On an optimization problem with nested constraints.
Discret. Appl. Math., 1990
1989
Algorithms for assignment problems on an array processor.
Parallel Comput., 1989
A randomized algorithm for fixed-dimensional linear programming.
Math. Program., 1989
Probabilistic Analysis of the Multidimensional Knapsack Problem.
Math. Oper. Res., 1989
On the number of hamilton cycles in a random graph.
J. Graph Theory, 1989
The Solution of Some Random NP-Hard Problems in Polynomial Expected Time.
J. Algorithms, 1989
On random minimum lenght spanning trees.
Comb., 1989
Survival time of a random graph.
Comb., 1989
1988
Reconstructing Truncated Integer Variables Satisfying Linear Congruences.
SIAM J. Comput., 1988
On the Complexity of Computing the Volume of a Polyhedron.
SIAM J. Comput., 1988
Probabilistic Analysis of a Relaxation for the <i>k</i>-Median Problem.
Math. Oper. Res., 1988
Edge-colouring random graphs.
J. Comb. Theory B, 1988
Finding hamilton cycles in sparse random graphs.
J. Comb. Theory B, 1988
An Algorithm for Finding Hamilton Cycles in Random Directed Graphs.
J. Algorithms, 1988
On the Random Construction of Heaps.
Inf. Process. Lett., 1988
Partitioning random graphs into large cycles.
Discret. Math., 1988
1987
On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients.
SIAM J. Comput., 1987
Large induced trees in sparse random graphs.
J. Comb. Theory B, 1987
Parallel Algorithms for Finding Hamilton Cycles in Random Graphs.
Inf. Process. Lett., 1987
Large holes in sparse random graphs.
Comb., 1987
An algorithm for finding Hamilton cycles in a random graph.
Comb., 1987
1986
On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem.
SIAM J. Comput., 1986
On linear programs with random costs.
Math. Program., 1986
Maximum matchings in a class of random graphs.
J. Comb. Theory B, 1986
Planar 3DM is NP-Complete.
J. Algorithms, 1986
On large matchings and cycles in sparse random graphs.
Discret. Math., 1986
Fast Solution of Some Random NP-Hard Problems
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
1985
Limit Distribution for the Existence of Hamiltonian Cycles in Random Bipartite Graphs.
Eur. J. Comb., 1985
The shortest-path problem for graphs with random arc-lengths.
Discret. Appl. Math., 1985
On the value of a random minimum spanning tree problem.
Discret. Appl. Math., 1985
On the complexity of partitioning graphs into connected subgraphs.
Discret. Appl. Math., 1985
An Algorithm for Finding a Matroid Basis which Maximizes the Products of the Weights of the Elements.
BIT, 1985
1984
Hamiltonian cycles in random regular graphs.
J. Comb. Theory B, 1984
A Partitioning Algorithm for Minimum Weighted Euclidean Matching.
Inf. Process. Lett., 1984
Linear Congruential Generators Do Not Produce Random Sequences
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
1983
Corrigendum: Algebraic Linear Programming.
Math. Oper. Res., 1983
On the existence of Hamiltonian cycles in a class of random graphs.
Discret. Math., 1983
On the quadratic assignment problem.
Discret. Appl. Math., 1983
An extension of Christofides heuristic to the k-person travelling salesman problem.
Discret. Appl. Math., 1983
1982
On the worst-case performance of some algorithms for the asymmetric traveling salesman problem.
Networks, 1982
Algebraic Linear Programming.
Math. Oper. Res., 1982
On the connectivity of random m-orientable graphs and digraphs.
Comb., 1982
1980
Probabilistic analysis of some euclidean clustering problems.
Discret. Appl. Math., 1980
1979
An algorithm for algebraic assignment problems.
Discret. Appl. Math., 1979
1976
Shortest path algorithms for knapsack type problems.
Math. Program., 1976
1974
A bilinear programming formulation of the 3-dimensional assignment problem.
Math. Program., 1974
A cost function property for plant location problems.
Math. Program., 1974
