Search results for "random graphs"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Alan M. Frieze, Santosh Vempala, Juan Vera	Logconcave random graphs.	STOC	2008	DBLP DOI BibTeX RDF	random graphs
3	Hariharan Narayanan	Geographic gossip on geometric random graphs via affine combinations.	PODC	2007	DBLP DOI BibTeX RDF	affine combinations, geometric random graphs, gossip algorithms
3	James F. Lynch	Convergence law for random graphs with specified degree sequence.	ACM Trans. Comput. Log.	2005	DBLP DOI BibTeX RDF	random graphs, Finite model theory
3	Robert Elsässer, Leszek Gasieniec	Radio communication in random graphs: extended abstract.	SPAA	2005	DBLP DOI BibTeX RDF	broadcasting, random graphs, radio networks, communication algorithms
3	C. R. Subramanian	Minimum Coloring Random and Semi-Random Graphs in Polynomial Expected Time.	FOCS	1995	DBLP DOI BibTeX RDF	minimum coloring random graphs, semi-random graphs, polynomial expected time, k-coloring, worst-case model, computational complexity, graph theory, vertices, graph colouring
2	Mohsen Bayati, David Gamarnik, Prasad Tetali	Combinatorial approach to the interpolation method and scaling limits in sparse random graphs.	STOC	2010	DBLP DOI BibTeX RDF	scaling limit, constraint satisfaction problems, random graphs, partition function
2	Mohsen Bayati, Andrea Montanari, Amin Saberi	Generating random graphs with large girth.	SODA	2009	DBLP DOI BibTeX RDF
2	Carsten Witt	Greedy Local Search and Vertex Cover in Sparse Random Graphs.	TAMC	2009	DBLP DOI BibTeX RDF
2	Phokion G. Kolaitis, Swastik Kopparty	Random graphs and the parity quantifier.	STOC	2009	DBLP DOI BibTeX RDF	0-1 law, AC0, modular convergence, first-order logic
2	Marc Lelarge	Efficient control of epidemics over random networks.	SIGMETRICS/Performance	2009	DBLP DOI BibTeX RDF	vaccination, random graphs, epidemics
2	Nilesh N. Dalvi	Query Evaluation on a Database Given by a Random Graph.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Asymptotic probabilities, Random graphs, Conjunctive queries
2	Jean-Jacques Daudin, Franck Picard, Stéphane Robin	A mixture model for random graphs.	Statistics and Computing	2008	DBLP DOI BibTeX RDF	Mixture models, Random graphs, Variational method
2	Md. Abdur Razzaque, Choong Seon Hong, Mohammad Abdullah-Al-Wadud, Oksam Chae	A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs.	WALCOM	2008	DBLP DOI BibTeX RDF	Boolean Matrix, Graph Diameter, Computational Complexity, Random Graphs, Adjacency Matrix
2	Amin Coja-Oghlan, André Lanka	Partitioning Random Graphs with General Degree Distributions.	IFIP TCS	2008	DBLP DOI BibTeX RDF
2	Colin Cooper, Alan M. Frieze	Random Walks on Random Graphs.	NanoNet	2008	DBLP DOI BibTeX RDF
2	Noga Alon, Asaf Nussboim	k-Wise Independent Random Graphs.	FOCS	2008	DBLP DOI BibTeX RDF
2	Shankar Bhamidi, Guy Bresler, Allan Sly	Mixing Time of Exponential Random Graphs.	FOCS	2008	DBLP DOI BibTeX RDF
2	Elchanan Mossel, Allan Sly	Rapid mixing of Gibbs sampling on graphs that are sparse on average.	SODA	2008	DBLP DOI BibTeX RDF	Erd?s-Rényi random graphs, Glauber dynamics, Gibbs samplers, mixing time, Ising model
2	Paul Beame, Russell Impagliazzo, Ashish Sabharwal	The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs.	Computational Complexity	2007	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17
2	Martin Pelikan, Rajiv Kalapala, Alexander K. Hartmann	Hybrid evolutionary algorithms on minimum vertex cover for random graphs.	GECCO	2007	DBLP DOI BibTeX RDF	minimum vertex cover, genetic algorithm, simulated annealing, branch and bound, hierarchical BOA
2	Steven P. Levitan	You Can Get There From Here: Connectivity of Random Graphs on Grids.	DAC	2007	DBLP DOI BibTeX RDF
2	Esteban Arcaute, Ning Chen, Ravi Kumar, David Liben-Nowell, Mohammad Mahdian, Hamid Nazerzadeh, Ying Xu 0002	Deterministic Decentralized Search in Random Graphs.	WAW	2007	DBLP DOI BibTeX RDF
2	Thomas Erlebach, Alexander Hall, Matús Mihalák	Approximate Discovery of Random Graphs.	SAGA	2007	DBLP DOI BibTeX RDF
2	Yael Dekel, James R. Lee, Nathan Linial	Eigenvectors of Random Graphs: Nodal Domains.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
2	Antoine Gerschenfeld, Andrea Montanari	Reconstruction for Models on Random Graphs.	FOCS	2007	DBLP DOI BibTeX RDF
2	Furuzan Atay Onat, Ivan Stojmenovic	Generating Random Graphs for Wireless Actuator Networks.	WOWMOM	2007	DBLP DOI BibTeX RDF
2	George Giakkoupis, Vassos Hadzilacos	On the complexity of greedy routing in ring-based peer-to-peer networks.	PODC	2007	DBLP DOI BibTeX RDF	peer-to-peer, lower bound, coupling, random graphs, small-worlds, greedy routing
2	Jesse S. A. Bridgewater, P. Oscar Boykin, Vwani P. Roychowdhury	Balanced Overlay Networks (BON): An Overlay Technology for Decentralized Load Balancing.	IEEE Trans. Parallel Distrib. Syst.	2007	DBLP DOI BibTeX RDF	load balancing, Distributed computing, randomized algorithms, random walks, random graphs
2	Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtech Rödl, Mathias Schacht	Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions.	ICALP	2007	DBLP DOI BibTeX RDF	quasi-random graphs, Laplacian eigenvalues, Grothendieck’s inequality, regularity lemma, sparse graphs
2	Shai Avidan, Yael Moses, Yoram Moses	Centralized and Distributed Multi-view Correspondence.	International Journal of Computer Vision	2007	DBLP DOI BibTeX RDF	wide baseline stereo, distributed vision, distributed multi-camera system, fault tolerance, error correction, random graphs, correspondence, multi-view
2	Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki	Matching Algorithms Are Fast in Sparse Random Graphs.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
2	Alan M. Frieze	Random graphs.	SODA	2006	DBLP DOI BibTeX RDF
2	Amin Coja-Oghlan, Andreas Goerdt, André Lanka	Spectral Partitioning of Random Graphs with Given Expected Degrees.	IFIP TCS	2006	DBLP DOI BibTeX RDF
2	Gregory Valiant, Tim Roughgarden	Braess's paradox in large random graphs.	ACM Conference on Electronic Commerce	2006	DBLP DOI BibTeX RDF	Braess's paradox, random graphs, selfish routing
2	Robert Elsässer	On the communication complexity of randomized broadcasting in random-like graphs.	SPAA	2006	DBLP DOI BibTeX RDF	broadcasting, random graphs
2	Moez Draief, Ayalvadi J. Ganesh, Laurent Massoulié	Thresholds for virus spread on networks.	VALUETOOLS	2006	DBLP DOI BibTeX RDF	SIR epidemic, largest connected component, random graphs, spectral radius
2	Amin Coja-Oghlan	A spectral heuristic for bisecting random graphs.	SODA	2005	DBLP DOI BibTeX RDF
2	Mark K. Goldberg, D. Hollinger, Malik Magdon-Ismail	Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs.	WEA	2005	DBLP DOI BibTeX RDF
2	Moni Naor, Asaf Nussboim, Eran Tromer	Efficiently Constructible Huge Graphs That Preserve First Order Properties of Random Graphs.	TCC	2005	DBLP DOI BibTeX RDF
2	Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore	On the bias of traceroute sampling: or, power-law degree distributions in regular graphs.	STOC	2005	DBLP DOI BibTeX RDF	internet mapping, random graphs, power laws
2	Martin Nehéz, Daniel Olejár	An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques.	ISAAC	2005	DBLP DOI BibTeX RDF	dominating cliques, additive stretch routing scheme, random graphs, Interval routing
2	Michael Krivelevich, Benny Sudakov, Tibor Szabó	Triangle Factors In Sparse Pseudo-Random Graphs.	Combinatorica	2004	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C70, 05C80
2	Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki	Matching Algorithms Are Fast in Sparse Random Graphs.	STACS	2004	DBLP DOI BibTeX RDF
2	Francesc Serratosa, Alberto Sanfeliu	Distance Measures between Attributed Graphs and Second-Order Random Graphs.	SSPR/SPR	2004	DBLP DOI BibTeX RDF
2	Béla Bollobás, Oliver Riordan	The Phase Transition and Connectedness in Uniformly Grown Random Graphs.	WAW	2004	DBLP DOI BibTeX RDF
2	Anirban Dasgupta, John E. Hopcroft, Frank McSherry	Spectral Analysis of Random Graphs with Skewed Degree Distributions.	FOCS	2004	DBLP DOI BibTeX RDF
2	Haixia Jia, Cristopher Moore	How Much Backtracking Does It Take to Color Random Graphs? Rigorous Results on Heavy Tails.	CP	2004	DBLP DOI BibTeX RDF
2	Charles U. Martel, Van Nguyen	Analyzing Kleinberg's (and other) small-world Models.	PODC	2004	DBLP DOI BibTeX RDF	routing, random graphs, diameter, small-world network
2	Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari	Sharp thresholds For monotone properties in random geometric graphs.	STOC	2004	DBLP DOI BibTeX RDF	sharp thresholds, wireless networks, geometric random graphs
2	Terry Caelli, Serhiy Kosinov	An Eigenspace Projection Clustering Method for Inexact Graph Matching.	IEEE Trans. Pattern Anal. Mach. Intell.	2004	DBLP DOI BibTeX RDF	Inexact multisubgraph matching, eigenspace projections, correspondence clustering, random graphs, shape matching, eigendecomposition
2	Ján Gaso, Martin Nehéz	Stochastic cooperative distributed grammar systems and random graphs.	Acta Inf.	2003	DBLP DOI BibTeX RDF
2	Amin Coja-Oghlan, Cristopher Moore, Vishal Sanwalani	MAX k-CUT and Approximating the Chromatic Number of Random Graphs.	ICALP	2003	DBLP DOI BibTeX RDF
2	Amin Coja-Oghlan, Anusch Taraz	Colouring Random Graphs in Expected Polynomial Time.	STACS	2003	DBLP DOI BibTeX RDF
2	Amin Coja-Oghlan	The Lovász Number of Random Graphs.	RANDOM-APPROX	2003	DBLP DOI BibTeX RDF
2	James F. Lynch	Convergence Law for Random Graphs with Specified Degree Sequence.	LICS	2003	DBLP DOI BibTeX RDF
2	Martin Dietzfelbinger, Philipp Woelfel	Almost random graphs with simple hash functions.	STOC	2003	DBLP DOI BibTeX RDF	uniform hashing, hash function, random graphs, cuckoo hashing
2	Francesc Serratosa, René Alquézar, Alberto Sanfeliu	Estimating the Joint Probability Distribution of Random Vertices and Arcs by Means of Second-Order Random Graphs.	SSPR/SPR	2002	DBLP DOI BibTeX RDF
2	André Brinkmann, Kay Salzwedel, Christian Scheideler	Compact, adaptive placement schemes for non-uniform requirements.	SPAA	2002	DBLP DOI BibTeX RDF	adaptive hashing, balls into bins, non-uniform disks, random graphs, web caching, RAID, distributed data storage
2	Dimitris Achlioptas, Cristopher Moore	Almost all graphs with average degree 4 are 3-colorable.	STOC	2002	DBLP DOI BibTeX RDF	threshold phenomena, graph coloring, random graphs
2	Josep Díaz, Jordi Petit, Maria J. Serna	A survey of graph layout problems.	ACM Comput. Surv.	2002	DBLP DOI BibTeX RDF	Approximation algorithms, complexity, heuristics, embedding, layout, random graphs, parameterized complexity
2	Andrew D. Bagdanov, Marcel Worring	Fine-Grained Document Genre Classification Using First Order Random Graphs. (PDF / PS)	ICDAR	2001	DBLP DOI BibTeX RDF
2	Hirotaka Ono, Mutsunori Yagiura, Toshihide Ibaraki	An Index for the Data Size to Extract Decomposable Structures in LAD.	ISAAC	2001	DBLP DOI BibTeX RDF	logical analysis of data, decomposable functions, Boolean functions, random graphs, probabilistic analysis, computational learning theory
2	Ayalvadi J. Ganesh, Anne-Marie Kermarrec, Laurent Massoulié	SCAMP: Peer-to-Peer Lightweight Membership Service for Large-Scale Group Communication.	Networked Group Communication	2001	DBLP DOI BibTeX RDF	gossip-based probabilistic multicast, reliability, peer-to-peer, Scalability, group communication, random graphs, membership
2	Joel Spencer, Gábor Tardos	Ups and Downs of First Order Sentences on Random Graphs.	Combinatorica	2000	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05C80, 60F20
2	Béla Bollobás, Andrew Thomason	The Structure of Hereditary Properties and Colourings of Random Graphs.	Combinatorica	2000	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05C80, 05C15, 05C75
2	C. R. Subramanian	Coloring Sparse Random Graphs in Polynominal Average Time.	ESA	2000	DBLP DOI BibTeX RDF
2	Noga Alon, Michael Krivelevich, Benny Sudakov	List Coloring of Random and Pseudo-Random Graphs.	Combinatorica	1999	DBLP DOI BibTeX RDF	AMS Subject Classification (1991) Classes: 05C80, 05C15
2	Shmuel Lifsches, Saharon Shelah	Random graphs in the monadic theory of order.	Arch. Math. Log.	1999	DBLP DOI BibTeX RDF
2	Uriel Feige, Joe Kilian	Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs.	FOCS	1998	DBLP DOI BibTeX RDF	Graph Coloring, Semidefinite Programming, Independent Sets
2	Michele Flammini, Jan van Leeuwen, Alberto Marchetti-Spaccamela	The Complexity of Interval Routing on Random Graphs.	MFCS	1995	DBLP DOI BibTeX RDF
2	Sotiris E. Nikoletseas, Krishna V. Palem, Paul G. Spirakis, Moti Yung	Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing.	ICALP	1994	DBLP DOI BibTeX RDF
2	C. R. Subramanian	Improved Algorithms for Coloring Random Graphs.	ISAAC	1994	DBLP DOI BibTeX RDF
2	C. R. Subramanian, C. E. Veni Madhavan	Coloring Semi-Random Graphs in Polynomial Expected Time.	FSTTCS	1994	DBLP DOI BibTeX RDF
2	Sotiris E. Nikoletseas, Paul G. Spirakis	Near-Optimal Dominating Sets in Dense Random Graphs in Polynomial Expected Time.	WG	1993	DBLP DOI BibTeX RDF
2	Martin Fürer, C. R. Subramanian, C. E. Veni Madhavan	Coloring Random Graphs in Polynomial Expected Time.	ISAAC	1993	DBLP DOI BibTeX RDF
2	Zvi M. Kedem, Krishna V. Palem, Grammati E. Pantziou, Paul G. Spirakis, Christos D. Zaroliagis	Fast Parallel Algorithms for Coloring Random Graphs.	WG	1991	DBLP DOI BibTeX RDF
2	Ludek Kucera	A Generalized Encryption Scheme Based on Random Graphs.	WG	1991	DBLP DOI BibTeX RDF
2	James F. Lynch	Probabilities of Sentences about Very Sparse Random Graphs	FOCS	1990	DBLP DOI BibTeX RDF	first-order sentence, very sparse random graphs, edge probability, fixed positive integer
1	Hao Huang, Choongbum Lee, Benny Sudakov	Bandwidth theorem for random graphs.	J. Comb. Theory, Ser. B	2012	DBLP DOI BibTeX RDF
1	Jing He, Hongyu Liang	On rainbow-k-connectivity of random graphs.	Inf. Process. Lett.	2012	DBLP DOI BibTeX RDF
1	Carsten Witt	Analysis of an iterated local search algorithm for vertex cover in sparse random graphs.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
1	Pu Gao, Yi Su, Nicholas C. Wormald	Induced subgraphs in sparse random graphs with given degree sequences.	Eur. J. Comb.	2012	DBLP DOI BibTeX RDF
1	Fiachra Knox, Daniela Kühn, Deryk Osthus	Approximate Hamilton decompositions of random graphs.	Random Struct. Algorithms	2012	DBLP DOI BibTeX RDF
1	Martin Dietzfelbinger, Hendrik Peilke, Michael Rink	A More Reliable Greedy Heuristic for Maximum Matchings in Sparse Random Graphs	CoRR	2012	DBLP BibTeX RDF
1	Antoine Allard, Laurent Hébert-Dufresne, Pierre-André Noël, Vincent Marceau, Louis J. Dubé	Bond percolation on a class of correlated and clustered random graphs	CoRR	2012	DBLP BibTeX RDF
1	Jaideep Ray, Ali Pinar, C. Seshadhri	Are we there yet? When to stop a Markov chain while generating random graphs	CoRR	2012	DBLP BibTeX RDF
1	Tadashi Wadayama, Yuki Fujii	A Coding Theoretic Approach for Evaluating Accumulate Distribution on Minimum Cut Capacity of Weighted Random Graphs	CoRR	2012	DBLP BibTeX RDF
1	Qianqian Xu, Qingming Huang, Tingting Jiang, Bowei Yan, Weisi Lin, Yuan Yao	HodgeRank on Random Graphs for Subjective Video Quality Assessment.	IEEE Transactions on Multimedia	2012	DBLP DOI BibTeX RDF
1	Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski	Universality of Random Graphs.	SIAM J. Discrete Math.	2012	DBLP DOI BibTeX RDF
1	Yong Gao	Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs.	Discrete Applied Mathematics	2012	DBLP DOI BibTeX RDF
1	Hervé Daudé, Conrado Martínez, Vonjy Rasendrahasina, Vlady Ravelomanana	The MAX-CUT of sparse random graphs.	SODA	2012	DBLP BibTeX RDF
1	Martin Nehéz, Daniel Olejár, Michal Demetrian	A Detailed Study of the Dominating Cliques Phase Transition in Random Graphs.	TAMC	2012	DBLP DOI BibTeX RDF
1	Domingos Dellamonica Jr., Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski	An Improved Upper Bound on the Density of Universal Random Graphs.	LATIN	2012	DBLP DOI BibTeX RDF
1	Zhongmei Yao, Daren B. H. Cline, Dmitri Loguinov	On superposition of heterogeneous edge processes in dynamic random graphs.	INFOCOM	2012	DBLP DOI BibTeX RDF
1	Torsten Mütze, Reto Spöhel, Henning Thomas	Small subgraphs in random graphs and the power of multiple choices.	J. Comb. Theory, Ser. B	2011	DBLP DOI BibTeX RDF
1	Luca Gugelmann, Reto Spöhel	On Balanced Coloring Games in Random Graphs.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Y. Kohayakawa, P. B. Konstadinidis, G. O. Mota	On an anti-Ramsey property of random graphs.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid	Largest sparse subgraphs of random graphs.	Electronic Notes in Discrete Mathematics	2011	DBLP DOI BibTeX RDF
1	Svante Janson	Quasi-random graphs and graph limits.	Eur. J. Comb.	2011	DBLP DOI BibTeX RDF
1	Elizabeth Beer, James Allen Fill, Svante Janson, Edward R. Scheinerman	On Vertex, Edge, and Vertex-Edge Random Graphs.	Electr. J. Comb.	2011	DBLP BibTeX RDF