scientific article
From MaRDI portal
zbMath0567.05042MaRDI QIDQ3682518
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (05Cxx)
Related Items
Sharp thresholds of graph properties, and the $k$-sat problem, Percolation on spatial anisotropic networks*, Quasi-Random Set Systems, A heuristic for decomposing traffic matrices in TDMA satellite communication, A study on properties of random interval graphs and Erdős Rényi graph 𝒢(n, 2/3), Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability, Binary Covering Arrays and Existentially Closed Graphs, The random linear bottleneck assignment problem, Perfect matchings in random subgraphs of regular bipartite graphs, Rankable distributions do not provide harder instances than uniform distributions, Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space, Complex networks for community detection of basketball players, On Interval Routing Schemes and treewidth, Localization of eigenvectors in random graphs, Unnamed Item, Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}, Two typical analytic models for reverse bond percolation on real networks, Unnamed Item, Finite length spectra of random surfaces and their dependence on genus, Mixing Rates for a Random Walk on the Cube, Near-optimal dominating sets in dense random graphs in polynomial expected time, Average case analysis of fully dynamic connectivity for directed graphs, A random graph growth model, Statistics of finite degree covers of torus knot complements, Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\), Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems, Lower bounds for sense of direction in regular graphs, Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing, Coloring graphs with fixed genus and girth, Some problems in analysis of discretizations of continuous dynamical systems, An analytic approach to sparse hypergraphs: hypergraph removal, On the number of points in general position in the plane, Size Ramsey numbers for some regular graphs, Size Ramsey numbers for some regular graphs, A generalization of maximal independent sets, One-dimensional asymptotic classes of finite structures, On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes, On approximating the longest path in a graph, The diameter of sparse random graphs, The giant component threshold for random regular graphs with edge faults H. Prodinger, On the growth of components with non-fixed excesses, Random regular graphs with edge faults: Expansion through cores, Geometrical structure of the neuronal network of Caenorhabditis elegans, Improved bounds on the sample complexity of learning, Complexity classification of some edge modification problems, Spectral properties of the \(k\)-body embedded Gaussian ensembles of random matrices., Fractals in small-world networks with time-delay, Growing random networks with fitness, A model for the evolution of economic systems in social networks, Recommendation systems: A probabilistic analysis, Resilience for the Littlewood-Offord problem, Arbitrary Threshold Widths for Monotone, Symmetric Properties, The size-Ramsey number of trees, A priori optimization for the probabilistic maximum independent set problem, Statistical mechanics methods and phase transitions in optimization problems, Common pattern formation, modularity and phase transitions in a gene network model of morphogenesis, Resilience for the Littlewood-Offord problem, Almost all graphs with average degree 4 are 3-colorable, Near-perfect token distribution, Infinitary logic for computer science, On the singularity of random matrices with independent entries, Характеристики случайных систем дискретных уравнений при неравновероятной выборке неизвестных, Совместность случайных систем уравнений с неравновероятной выборкой двузначных неизвестных, Poisson approximation of the length spectrum of random surfaces, Most graphs are knotted, The effects of community interactions and quarantine on a complex network, Minors of a random binary matroid, Every monotone graph property has a sharp threshold, Zero-One Laws for Sparse Random Graphs, Broadcasting in random graphs, Гигантская компонента в случайных дистанционных графах специального вида, On the probability of planarity of a random graph near the critical point, A Random Graph With a Subcritical Number of Edges, The first eigenvalue of a Riemann surface, Central limit theorem for fluctuations of linear eigenvalue statistics of large random graphs, Tree decompositions and social graphs, Unnamed Item, A Tipping Point for the Planarity of Small and Medium Sized Graphs, Discrete Graphs – A Paradigm Model for Quantum Chaos, Periods of iterated rational functions, Size of the largest cluster under zero-range invariant measures, Bins and balls: Large deviations of the empirical occupancy process, Complete on average Boolean satisfiability, Algorithms for the fixed linear crossing number problem, Disjointly representing set systems, Optimal attack strategy of complex networks based on tabu search, A small-world and scale-free network generated by Sierpinski pentagon, Positive and negative effects of social impact on evolutionary vaccination game in networks, Forbidden subgraphs in connected graphs, Bounds on the max and min bisection of random cubic and random 4-regular graphs, Sandwiching random graphs: universality between random graph models, A sharp threshold in proof complexity yields lower bounds for satisfiability search, Reconstruction methods for networks: the case of economic and financial systems, Reconstruction of distance hereditary 2-connected graphs, The genus of a random graph, Epidemics on plants: modeling long-range dispersal on spatially embedded networks, A family of antipodal distance-regular graphs related to the classical Preparata codes, Searching for acyclic orientations of graphs, Close-to-optimal and near-optimal broadcasting in random graphs, A simple a. s. correct algorithm for deciding if a graph has a perfect matching, Defect Sauer results, On key storage in secure networks, Collapsing effects in numerical simulation of a class of chaotic dynamical systems and random mappings with a single attracting centre, On the asymptotic behavior of the independence number of a random \((n,n)\)-tree, The random-cluster model on the complete graph, The impact of initial cooperation fraction on the evolutionary fate in a spatial Prisoner's dilemma game, Counting \(H\)-free graphs, Walks on random digraphs, Diophantine networks, Perfect hashing, No NP problems averaging over ranking of distributions are harder, A lower bound on branching programs reading some bits twice, Game theoretical modelling of a dynamically evolving network. I: General target sequences, Continuum percolation of wireless ad hoc communication networks, The most general set and chaos graph, Analysis of edge deletion processes on faulty random regular graphs., Small maximal matchings in random graphs., Generalized satisfiability problems: Minimal elements and phase transitions., Principles of statistical mechanics of uncorrelated random networks, A Berry-Esseen bound with applications to vertex degree counts in the Erdős-Rényi random graph, Geographical embedding of scale-free networks, Length of optimal path in random networks with strong disorder, Analysis of greedy algorithms on graphs with bounded degrees, Phase transition in the spanning-hyperforest model on complete hypergraphs, How to survive while visiting a graph, A stochastically quasi-optimal search algorithm for the maximum of the simple random walk, The degree analysis of an inhomogeneous growing network with two types of vertices, Modelling high pathogenic avian influenza outbreaks in the commercial poultry industry, Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists, Change point detection in network models: preferential attachment and long range dependence, Average independence polynomials, Structure of large random hypergraphs, Branching processes, and random-cluster measures on trees, Trapping on modular scale-free and small-world networks with multiple hubs, Random walks between leaves of random networks, ``Immunetworks, intersecting circuits and dynamics, Of bits and wows: a Bayesian theory of surprise with applications to attention, Random catalytic reaction networks, Expanding and forwarding, On evidence absorption for belief networks, Pseudo-random hypergraphs, Transversal numbers of uniform hypergraphs, Degree multiplicities and independent sets in \(K_ 4\)-free graphs, A simple linear expected time algorithm for finding a Hamilton path, The harmonic mean formula for probabilities of unions: Applications to sparse random graphs, A bidirectional shortest-path algorithm with good average-case behavior, The star arboricity of graphs, Parallel graph algorithms that are efficients on average, Renormalization group analysis of the small-world network model, Lower bounds for weak sense of direction, The integrity of a cubic graph, Bounds for optimal coverings, The Vapnik-Chervonenkis dimension of a random graph, An analysis of Monte Carlo algorithm for estimating the permanent, The multichromatic numbers of some Kneser graphs, The oriented cycle game, Euler circuits and DNA sequencing by hybridization, Random subgraphs of Cayley graphs over \(p\)-groups, Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs, Nowhere-zero flows in random graphs, The extremal function for complete minors, Regular graphs with no homomorphisms onto cycles, On the largest component of the random graph at a nearcritical stage, Graph imperfection. II, On the robustness of interconnections in random graphs: a symbolic approach., How many probes are needed to compute the maximum of a random walk?, Scalable secure storage when half the system is faulty, Packet transport and load distribution in scale-free network models, Human sexual contact network as a bipartite graph, Statistical evaluation of algebraic constraints for social networks, A perspective on certain polynomial-time solvable classes of satisfiability, The width of random subsets of Boolean lattices, Complex scale-free networks, Evolution of the social network of scientific collaborations, The complexity of theory revision, Random 2-SAT and unsatisfiability, Pregeometric concepts on graphs and cellular networks as possible models of space-time at the Planck-scale, Maximum induced matchings of random cubic graphs, Wavelength routing in optical networks of diameter two, The phase transition in a random hypergraph, Consensus dynamics on random rectangular graphs, Threshold circuits of bounded depth, Total domination in regular graphs, Critical Density Thresholds in Distributed Wireless Networks, On the cover time and mixing time of random geometric graphs, Non-consensus opinion models on complex networks, Residue centrality in alpha helical polytopic transmembrane protein structures, Another proof of Wright's inequalities, Networks Synchronizability, Local Dynamics and Some Graph Invariants, Width versus size in resolution proofs, Robustness of networks with assortative dependence groups, Large independent sets in regular graphs of large girth, Isoperimetric numbers of graphs, Chromatic number versus chromatic number in graphs with bounded clique number, Statistical Physics and Network Optimization Problems, Stochasticity of disease spreading derived from the microscopic simulation approach for various physical contact networks, The unsatisfiability threshold revisited, Current trends in asymptotics: Some problems and some solutions, Bipartite structure of all complex networks, Shells structure in uncorrelated scale-free networks, Limit theorems and coexistence probabilities for the Curie-Weiss Potts model with an external field, Unnamed Item, Fairest edge usage and minimum expected overlap for random spanning trees, PALO: a probabilistic hill-climbing algorithm, Complex networks: structure and dynamics, Evolving protein interaction networks through gene duplication, Centers of complex networks, Phase transitions and the search problem, Generating hard satisfiability problems, An empirical study of phase transitions in binary constraint satisfaction problems, Refining the phase transition in combinatorial search, Locating the phase transition in binary constraint satisfaction problems, A study of complexity transitions on the asymmetric traveling salesman problem, Critical behavior in the computational cost of satisfiability testing, Problem structure heuristics and scaling behavior for genetic algorithms, Spread of two linked social norms on complex interaction networks, Effects of neighbourhood size and connectivity on the spatial continuous prisoner's dilemma, Examining the potential effects of species aggregation on the network structure of food webs, Dynamical patterns of epidemic outbreaks in complex heterogeneous networks, Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights, The growth and form of tunnelling networks in ants, On an adjacency property of almost all tournaments, Hamilton decompositions of regular expanders: applications, Quantification and statistical analysis of topological features of recursive trees, Unlacing hypercube percolation: a survey, On the tree-depth of random graphs, The community structure of human cellular signaling network, Exponential-family models of random graphs: inference in finite, super and infinite population scenarios, The distribution of the maximum vertex degree in random planar maps, Finding large cliques in sparse semi-random graphs by simple randomized search heuristics, Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs, Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit, The Canophy graph and level statistics for random operators on trees, Graphs with the \(n\)-e.c. adjacency property constructed from affine planes, Asymptotics of the number of threshold functions and the singularity probability of random \( \{\pm 1\}\)-matrices, Random matrix theory over finite fields, Multiobjective Bak-Sneppen model on a small-world network, A probabilistic approach to value sets of polynomials over finite fields, Induced gelation in a two-site spatial coagulation model, Radio communication in random graphs, Ramsey-type theorems for metric spaces with applications to online problems, A survey of homogeneous structures, Diameter, connectivity, and phase transition of the uniform random intersection graph, Rainbow \(k\)-connectivity of random bipartite graphs, Occupancy problems and random algebras, On 3-pushdown graphs with large separators, Giant Component in Random Multipartite Graphs with Given Degree Sequences, The distribution of clusters in random graphs, A phase transition in the random transposition random walk, From Graph Theory to Models of Economic Networks. A Tutorial, A Dynamic Model of Segregation in Small-World Networks, Fluctuations of the free energy in the diluted SK-model, Random Hypergraph Irregularity, Applications of the variance of final outbreak size for disease spreading in networks, Spectral edge in sparse random graphs: upper and lower tail large deviations, Connector-breaker games on random boards, Almost sure Assouad-like dimensions of complementary sets, Model for cascading failures in congested internet, Coloring graphs without bichromatic cycles or paths, Competition and fitness in one-mode collaboration network, Lengths of closed geodesics on random surfaces of large genus, Distance-Based Clique Relaxations in Networks: s-Clique and s-Club, The Chain of Infection, Contacts, and Model Parametrization, Maximum colored trees in edge-colored graphs, Mixing time of vertex-weighted exponential random graphs, A note on log-concave random graphs, New theoretical bounds and constructions of permutation codes under block permutation metric, On a game of chance in Marc Elsberg's thriller ``GREED, Average case analysis of fully dynamic reachability for directed graphs, Towards a dynamical model for wireless sensor networks, On the spectrum and number of convex sets in graphs, A hierarchy of randomness for graphs, On the typical case complexity of graph optimization, Threshold properties of random Boolean constraint satisfaction problems, Analytic description of the phase transition of inhomogeneous multigraphs, Solution to the Mean King's Problem in Prime Power Dimensions Using Discrete Tomography, Epidemic control analysis: designing targeted intervention strategies against epidemics propagated on contact networks, On the number of components of fixed size in a random \(A\)-mapping, Communication complexity of quasirandom rumor spreading, Ample simplicial complexes, On the typical values of the cross-correlation measure, Rulers and slaves in a random social group, Generic case complexity of the graph isomorphism problem, Coloring random graphs, Quantum ergodicity for quantum graphs without back-scattering, On the runtime and robustness of randomized broadcasting, Minimum vertex cover in generalized random graphs with power law degree distribution, Strong uniform times and finite random walks, Poisson convergence and Poisson processes with applications to random graphs, Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, Enhancing complex network controllability by minimum link direction reversal, The cross-correlation measure of families of finite binary sequences: limiting distributions and minimal values, Mathematical programming approaches for classes of random network problems, 3-star factors in random \(d\)-regular graphs, Properties of regular graphs with large girth via local algorithms, Gelation in coagulating systems, Diffusion, fragmentation and merging: rate equations, distributions and critical points, The evolution of fairness in the coevolutionary ultimatum games, \(k\)-core architecture and \(k\)-core percolation on complex networks, Anomalous electrical and frictionless flow conductance in complex networks, Threshold for monotone symmetric properties through a logarithmic Sobolev inequality, Poisson-Dirichlet distribution for random Belyi surfaces, Cubic and quadruple Paley graphs with the \(n\)-e.c. property, On avoiding odd partial Latin squares and \(r\)-multi Latin squares, Finite covers of random 3-manifolds, The well-covered dimension of random graphs, Agent-based randomized broadcasting in large networks, Reconstructing graphs from size and degree properties of their induced \(k\)-subgraphs, Graph factors and factorization: 1985--2003: a survey, Almost every graph is vertex-oblique, Planning as satisfiability: heuristics, The performance model of dynamic virtual organization (VO) formations within grid computing context, Grouping objects in multi-band images using an improved eigenvector-based algorithm, Birth and growth of multicyclic components in random hypergraphs, Random graph asymptotics on high-dimensional tori, The evolution of genetic topologies, Spectral distributions of adjacency and Laplacian matrices of random graphs, On dissemination thresholds in regular and irregular graph classes, On certain functionals of the maximum of Brownian motion and their applications, Fast uniform generation of regular graphs, On rainbow-\(k\)-connectivity of random graphs, The first cycles in an evolving graph, Finiteness of outer automorphism groups of random right-angled Artin groups, An evolution of interval graphs, Eigenvalues and singular values of certain random matrices, The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected, Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings, On the growth of random knapsacks, Effect of scale on long-range random graphs and chromosomal inversions, A simply obtained asymptotic expansion for the probability that a random mapping is connected, Lower bounds for recognizing small cliques on CRCW PRAM's, 0-1 laws and decision problems for fragments of second-order logic, Optimal and near-optimal broadcast in random graphs, On the independence number of random graphs, Right-convergence of sparse random graphs, Maximum entropy principle for Kaniadakis statistics and networks, The combined effect of connectivity and dependency links on percolation of networks, Optimal covers with Hamilton cycles in random graphs, Saturation number of fullerene graphs, Two sufficient conditions for Poisson approximations in the ferromagnetic Ising model, On a small class of Boolean sums, A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law, Local and global synchronization in general complex dynamical networks with delay coupling, \(H(n)\)-factors in random graphs, Risk assessment for infectious disease and its impact on voluntary vaccination behavior in social networks, Vulnerability and controllability of networks of networks, Probabilistic inequalities for evaluating structural network measures, On depth first search trees in \(m\)-out digraphs, The sequential generation of random \(f\)-graphs. Distributions and predominant types of edge maximal \(f\)-graphs with \(f>4\), Hypercube percolation, Asymptotic enumeration of 2-covers and line graphs, Random preorders and alignments, The coupling method for inhomogeneous random intersection graphs., Passive stability and synchronization of complex spatio-temporal switching networks with time delays, High-dimensional structure estimation in Ising models: local separation criterion, An almost quadratic bound on vertex Folkman numbers, Highly symmetric expanders, Covering arrays from cyclotomy, Connectivity distribution and attack tolerance of general networks with both preferential and random attachments, Sharp thresholds for Hamiltonicity in random intersection graphs, Phase transition and finite-size scaling in the vertex-cover problem, A program generating homogeneous random graphs with given weights, Low eigenvalues of Laplacian matrices of large random graphs, Geography of local configurations, Graphs whose every transitive orientation contains almost every relation, Communication tree problems, Corners in tree-like tableaux, Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly, On the distribution of the domination number for random class cover catch digraphs, Approximating the minimum independent dominating set in perturbed graphs, An upper bound on the sample complexity of PAC-learning halfspaces with respect to the uniform distribution, Large random graphs in pseudo-metric spaces, Symmetric block bases in finite-dimensional normed spaces, The distribution of extremes in the degree sequence: A Gumbel distribution approach, Connected domination of regular graphs, An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm, Edge irregular total labellings for graphs of linear size, Nonuniform recursive trees with vertex attraction depending on their labels, How to make a graph bipartite, Lattice bandwidth of random graphs, Autocorrelation on words and its applications. Analysis of suffix trees by string-ruler approach, Sparse matrix vector multiplication on distributed architectures: Lower bounds and average complexity results, The edge-forwarding index or orbital regular graphs, Heuristics for laying out information graphs, Finding a target subnetwork in sparse networks with random faults, A random clustering process, Hypergraphs and sharpened sieve inequalities, Listing graphs that satisfy first-order sentences, A new adaptive multi-start technique for combinatorial global optimizations, Phase transition phenomena in random discrete structures, Metric inference for social networks, Probabilistic models in cluster analysis, On an approximation measure founded on the links between optimization and polynomial approximation theory, Brownian excursions, critical random graphs and the multiplicative coalescent, Hypergraph colouring and the Lovász local lemma, A note on local colorings of graphs, Folding of fuzzy torus and fuzzy graphs, A note on the edge-reconstruction of \(K_{1,m}\)-free graphs, Epidemics in a population with social structures, Generic properties of combinatory maps: Neutral networks of RNA secondary structures, Walk generating functions and spectral measures of infinite graphs, Almost perfect matchings in random uniform hypergraphs, The number of connected sparsely edged uniform hypergraphs, Edge-colouring random graphs, Modified binomial and Poisson distributions with applications in random mapping theory, On subspaces spanned by random selections of \(\pm 1\) vectors, Variations on the Ising problem, Asymptotic normality of graph statistics, Tight approximations for resource constrained scheduling and bin packing, Sorting in rounds, Random induced subgraphs of generalized \(n\)-cubes, Approximate counting, uniform generation and rapidly mixing Markov chains, Asymptotic enumeration of convex polygons, Patterns and invasions of evolutionarily stable strategies, Subgraph counts in random graphs using incomplete U-statistics methods, Constructive bounds for a Ramsey-type problem, The linear arboricity of graphs, The isoperimetric number of random regular graphs, A new upper bound for the list chromatic number, Maximal induces trees in sparse random graphs, The existence of uniquely \(-G\) colourable graphs, On some conjectures of Graffiti, Almost all Cayley graphs have diameter 2, Triad count statistics, A graph property not satisfying a ``zero-one law, Three hundred million points suffice, Bipartite dimensions and bipartite degrees of graphs, An experimental evaluation of local search heuristics for graph partitioning, On interval routing schemes and treewidth, On the double competition number, A graph-theoretic result for a model of neural computation, The hidden algorithm of Ore's theorem on Hamiltonian cycles, A probabilistic view of Datalog parallelization, Probabilistic combinatorial optimization problems on graphs: A new domain in operational research, Graphs without large triangle free subgraphs, Size and connectivity of the \(k\)-core of a random graph, Threshold functions for local properties of graphs: Triangles, Pancyclic Hamilton cycles in random graphs, On the largest strong components in \(m\)-out digraphs, On-line computation of minimal and maximal length paths, On the independence and chromatic numbers of random regular graphs, Kolmogorov complexity and random graphs, Expected parallel time and sequential space complexity of graph and digraph problems, The average parallel complexity of Cholesky factorization, Distanced graphs, On the number of maximum genus embeddings of almost all graphs, Infinitary logics and 0-1 laws, Matchings in random superpositions of bipartite trees, Convex hulls of dense balanced graphs, The construction of a set of recurrence which is not a set of strong recurrence, A linear time algorithm for graph partition problems, On small graphs with highly imperfect powers, Matching theory -- a sampler: From Dénes König to the present, Fuzzy graphs in the evaluation and optimization of networks, Analysis of minimal path routing schemes in the presence of faults, An optimal algorithm for generating minimal perfect hash functions, Thresholds for classes of intersection graphs, Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses, On large induced trees and long induced paths in sparse random graphs, Submaps of maps. I: General 0-1 laws, A Ramsey type problem concerning vertex colourings, Covering cubes by random half cubes, with applications to binary neural networks, On the density of subgraphs in a graph with bounded independence number, Empirically-derived estimates of the complexity of labeling line drawings of polyhedral scenes, The parallel complexity of approximating the high degree subgraph problem, Coalescent random forests, Elements of a theory of computer simulation. I, Weak measure extension axioms, Tree and forest weights and their application to nonuniform random graphs, Limit theorems for a random graph epidemic model, On the connectivity of random subsets of projective spaces, Fuzzy retraction and folding of fuzzy-orientable compact manifold, The existence of exactly \(m\)-coloured complete subgraphs, Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs, Combinatorics and connectionism, Folding of fuzzy graphs and fuzzy spheres, A processor efficient MIS algorithm on random graphs, Random Ramsey graphs for the four-cycle, Extremal problems and generalized degrees, A probabilistic upper bound for the edge identification complexity of graphs
