scientific article
From MaRDI portal
Publication:4004078
zbMath0767.05001MaRDI QIDQ4004078
Publication date: 18 September 1992
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Chromatic kernel and its applications, Randomization, derandomization and antirandomization: Three games, Approximations for the maximum acyclic subgraph problem, A probabilistic lower bound on the independence number of graphs, A problem of Füredi and Seymour on covering intersecting families by pairs, An \(O(n\log n)\) algorithm for finding dissimilar strings, Approximate Max \(k\)-Cut with subgraph guarantee, Coloring random graphs, Random walks supported on random points of \(Z/nZ\), Upper bounds for \(\alpha \)-domination parameters, Projections of the natural measure for percolation fractals, Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, Independent sets in graphs with triangles, Coloring and the Lovász local lemma, On the random greedy \(F\)-free hypergraph process, Streaming algorithms for independent sets in sparse hypergraphs, Sets of permutations that generate the symmetric group pairwise., Generic erasure correcting sets: bounds and constructions, A faster distributed protocol for constructing a minimum spanning tree, On the stabbing number of a random Delaunay triangulation, The number of Seymour vertices in random tournaments and digraphs, Limit velocity and zero-one laws for diffusions in random environment, On the variational distance of two trees, A simple population protocol for fast robust approximate majority, Tight bounds for FEC-based reliable multicast, Testing juntas, Average stretch analysis of compact routing schemes, Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks, Bipartite dimensions and bipartite degrees of graphs, Sperner type theorems with excluded subposets, On vertex independence number of uniform hypergraphs, A note on eigenvalue bounds for independence numbers of non-regular graphs, Domination in transitive colorings of tournaments, Pricing commodities, Two results on the digraph chromatic number, Scaling limits for internal aggregation models with multiple sources, On the complexity of asynchronous agreement against powerful adversaries, Fighting constrained fires in graphs, Convergence and approximation in potential games, Efficient methods for selfish network design, On the adjacent vertex-distinguishing acyclic edge coloring of some graphs, On the obfuscation complexity of planar graphs, Selfish splittable flows and NP-completeness, Domination number of graphs without small cycles, Solution of the minimum modulus problem for covering systems, Best monotone degree conditions for graph properties: a survey, Lower bounds for independence numbers of some locally sparse graphs, On the disconnection of a discrete cylinder by a biased random walk, Matching nuts and bolts faster, A phase transition for the minimum free energy of secondary structures of a random RNA, Information lower bounds via self-reducibility, A phase transition for the metric distortion of percolation on the hypercube, Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees, Clique partitions of complements of forests and bounded degree graphs, The \(k\)-tuple domination number revisited, Improved approximation algorithms for box contact representations, Optimal slope selection via expanders, A Kolmogorov complexity proof of the Lovász local lemma for satisfiability, The complexity of explicit constructions, The `Butterfly effect' in Cayley graphs with applications to genomics., Asymptotically optimal frugal colouring, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Pseudo-Boolean optimization, Coloring face hypergraphs on surfaces, Using the incompressibility method to obtain local Lemma results for Ramsey-type problems, A construction for Ramsey numbers for \(K_{m,n}\), Nonadaptive group testing with lies: probabilistic existence theorems, The linear arboricity of planar graphs with no short cycles, The power and limitations of static binary search trees with lazy finger, Domination in bipartite graphs, A solitaire game played on 2-colored graphs, Ramsey numbers involving graphs with large degrees, On the spectrum of projective norm-graphs, Random constructions and density results, A generalization of an independent set with application to \((K_q; k)\)-stable graphs, Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly, Finding occurrences of protein complexes in protein-protein interaction graphs, Broadcasting in dynamic radio networks, Progressions in sequences of nearly consecutive integers, A useful elementary correlation inequality. II, Covering cubes by random half cubes, with applications to binary neural networks, Bipartite Ramsey numbers involving large \(K_{n,n}\), 2-partition-transitive tournaments, The SAT-UNSAT transition for random constraint satisfaction problems, Near-optimal, distributed edge colouring via the nibble method, The parallel complexity of approximating the high degree subgraph problem, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Zero knowledge and the chromatic number, Approximating hyper-rectangles: Learning and pseudorandom sets, Estimating satisfiability, Random Sidon sequences, On a random graph evolving by degrees, On a graph colouring problem, The space complexity of approximating the frequency moments, Extracting randomness: A survey and new constructions, A strengthening of Brooks' theorem, Signed domination in regular graphs and set-systems, Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs, The independence number of graphs in terms of degrees, On sparse approximations to randomized strategies and convex combinations, Scheduling computations with provably low synchronization overheads, Lower bounds for off-line range searching, MODp-tests, almost independence and small probability spaces, Optimal flow through the disordered lattice, DEX: self-healing expanders, The asymptotic behavior of the correspondence chromatic number, Distributed scheduling for disconnected cooperation, Eternal domination and clique covering, Hard graphs for randomized subgraph exclusion algorithms, Neighborhood graphs and distributed Δ+1-coloring, A view from the bridge spanning combinatorics and probability, On the Random Greedy $F$-Free Hypergraph Process, On dependent randomized rounding algorithms, Learning juntas in the presence of noise, Large independent sets in regular graphs of large girth, The independence numbers of weighted graphs with forbidden cycles, Non-degenerate Hilbert cubes in random sets, Approachability with bounded memory, Phase transition in a random NK landscape model, The $\chi$-Ramsey Problem for Triangle-Free Graphs, On the Lovász Theta Function for Independent Sets in Sparse Graphs, Planarity and Genus of Sparse Random Bipartite Graphs, Obfuscated fuzzy Hamming distance and conjunctions from subset product problems, On 2-step and hop dominating sets in graphs, Random walk on barely supercritical branching random walk, Derandomized Construction of Combinatorial Batch Codes, Probably approximately optimal satisficing strategies, On Selkow's bound on the independence number of graphs, Aspects of the Kahane-Salem-Zygmund inequalities in Banach spaces, An elementary introduction to the geometry of quantum states with pictures, Forbidden Intersection Patterns in the Families of Subsets (Introducing a Method), An effective criterion and a new example for ballistic diffusions in random environment, On lines, joints, and incidences in three dimensions, Locally Dense Independent Sets in Regular Graphs of Large Girth—An Example of a New Approach, A counterexample of size 20 for the problem of finding a 3-dimensional stable matching with cyclic preferences, Discrepancy in arithmetic progressions, Arithmetic Progressions and Tic-Tac-Toe Games, On upper bounds for multiple domination numbers of graphs, A note on searching line arrangements and applications, Introduction to Testing Graph Properties, Global offensive alliances in graphs and random graphs, Maximal inequalities and their applications to orthogonal and Hadamard matrices, The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments, On the minimum load coloring problem, Coloring bipartite hypergraphs, The strongest facets of the acyclic subgraph polytope are unknown, A generalised upper bound for the \(k\)-tuple domination number, On Nonnegative Cosine Polynomials with Nonnegative Integral Coefficients, Better size estimation for sparse matrix products, Refinements of Goldbach's conjecture, and the generalized Riemann hypothesis, New potential functions for greedy independence and coloring, Power of \(k\) choices and rainbow spanning trees in random graphs, Chromatic capacity and graph operations, Upper and lower Ramsey bounds in bounded arithmetic, A lower bound for off-diagonal van der Waerden numbers, The almost surely shrinking yolk, A note on the Size-Ramsey number of long subdivisions of graphs, Unnamed Item, An approximation algorithm for counting contingency tables, Phase transition in random distance graphs on the torus, On the transient (T) condition for random walk in mixing environment, Simultaneous graph parameters: factor domination and factor total domination, Recognizing binary shuffle squares is \textsf{NP}-hard, Theory of chemical evolution of molecule compositions in the universe, in the Miller-Urey experiment and the mass distribution of interstellar and intergalactic molecules, GreedyMAX-type Algorithms for the Maximum Independent Set Problem, Signed and Minus Dominating Functions in Graphs, Bipartite Ramsey numbers of cycles for random graphs, Generating Random Networks Without Short Cycles, A Sample of Samplers: A Computational Perspective on Sampling, Basic Facts about Expander Graphs, Introduction to Testing Graph Properties, Matchings with few colors in colored complete graphs and hypergraphs, Multi-issue social learning, Every monotone graph property has a sharp threshold, Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns, Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers, Breaking an Identity-Based Encryption Scheme Based on DHIES, Distributed near-optimal matching, Explicit two-source extractors and resilient functions, Almost Optimal Bounds for Direct Product Threshold Theorem, Fourier decay for self-similar measures, A quantitative Lovász criterion for Property B, Super solutions of random \((3 + p)\)-SAT, Arity hierarchies, The linear arboricity of \(K_5\)-minor free graphs, Finding kings in tournaments, Tournaments and Semicomplete Digraphs, On the double Roman domination of graphs, On Dinur’s proof of the PCP theorem, On defining sets for projective planes, A hierarchy of randomness for graphs, Condorcet winning sets, Lower bounds for boxicity, Randomly finding independent sets in locally sparse graphs, On the size of partial block designs with large blocks, The resolution complexity of random graph \(k\)-colorability, Online concealed correlation and bounded rationality, Sharp concentration of hitting size for random set systems, Threshold Group Testing, The local cut lemma, Complexity of finding dense subgraphs, A dimension gap for continued fractions with independent digits -- the non stationary case, Boolean functions: influence, threshold and noise, Sandwiching random graphs: universality between random graph models, A sharp threshold in proof complexity yields lower bounds for satisfiability search, An improved bound for disjoint directed cycles, More on BPP and the polynomial-time hierarchy, A bound on the strong chromatic index of a graph, On nearest-neighbor graphs, Fractional v. integral covers in hypergraphs of bounded edge size, Hypergraph colouring and the Lovász local lemma, Multiple domination models for placement of electric vehicle charging stations in road networks, On the Ramsey number \(r(H+\overline{K_ n},K_ n)\), Some remarks on \((k-1)\)-critical subgraphs of \(k\)-critical graphs, Efficient massively parallel implementation of some combinatorial algorithms, The complexity of cover graph recognition for some varieties of finite lattices, Nearly perfect matchings in regular simple hypergraphs, Improved upper bounds for approximation by zonotopes, The complexity of parallel prefix problems on small domains, The abstract lace expansion, Computing sparse approximations deterministically, On acyclic colorings of graphs on surfaces, On embedding expanders into \(\ell_p\) spaces, Constructive bounds for a Ramsey-type problem, Applications of the crossing number, Comparison of independent, stratified and random covering sample schemes in optimization problems, Ramsey properties of random hypergraphs, Rounding algorithms for covering problems, The local density of triangle-free graphs, A lower bound for irredundant Ramsey numbers, Optimal bounds for the approximation of Boolean functions and some applications, Acyclic edge coloring of graphs with large girths, Probabilistic existence theorems in group testing, Bounded size components -- partitions and transversals., Distributed broadcast in radio networks of unknown topology., Constant time parallel sorting: An empirical view., Partitioning into graphs with only small components, On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma, Input locality and hardness amplification, Two sensitivity theorems in fuzzy integer programming., A Gale-Berlekamp permutation-switching problem in higher dimensions, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, A few logs suffice to build (almost) all trees. II, Max NP-completeness made easy, Isolation, matching, and counting uniform and nonuniform upper bounds, Computational indistinguishability: A sample hierarchy, On membership comparable sets, On complexity, representation and approximation of integral multicommodity flows, Bipartite Ramsey numbers of paths for random graphs, Roman domination in graphs., Distinguishing string selection problems., Reroute sequence planning in telecommunication networks and compact vector summation., Efficient decomposition of separable algebras., Noise stability of weighted majority, Sparse multipartite graphs as partition universal for graphs with bounded degree, Towards the linear arboricity conjecture, \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph, On stream ciphers with provable beyond-the-birthday-bound security against time-memory-data tradeoff attacks, Rigidity and separation indices of Paley graphs, Antipodality properties of finite sets in Euclidean space, On the degree of restrictions of \(q\)-valued logic vector functions to linear manifolds, Local statistics for random domino tilings of the Aztec diamond, Optimal data compression algorithm, Coloring graphs with sparse neighborhoods, Secure frameproof codes, key distribution patterns, group testing algorithms and related structures, Maximum antichains in random subsets of a finite set, Chromatic capacities of graphs and hypergraphs, Cellular telephone networks and random maps in hypergraphs, Inferring evolutionary trees with strong combinatorial evidence, Min-wise independent permutations, A near-optimal polynomial time algorithm for learning in certain classes of stochastic games, The Vapnik-Chervonenkis dimension of a random graph, An extremal problem for subset-sum-distinct sequences with congruence conditions, Sign-balanced covering matrices, Averaging sequences, deranged mappings, and a problem of Lampert and Slater, Measure and probability for concurrency theorists, On generalized Ramsey theory: The bipartite case, Nowhere-zero flows in random graphs, The extremal function for complete minors, Covering non-uniform hypergraphs, Choosability in random hypergraphs, Coloring face-hypergraphs of graphs on surfaces, Graph imperfection. II, On computing the diameter of a point set in high dimensional Euclidean space., On the robustness of interconnections in random graphs: a symbolic approach., On weighted vs unweighted versions of combinatorial optimization problems, On the decisional complexity of problems over the reals, Scalable secure storage when half the system is faulty, A perspective on certain polynomial-time solvable classes of satisfiability, A note on greedy algorithms for the maximum weighted independent set problem, Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number, Approximation algorithms for maximum linear arrangement, A manifesto for the computational method, An approximation algorithm for the maximization version of the two level uncapacitated facility location problem, Which problems have strongly exponential complexity?, Perfect information leader election in \(\log^*n+O(1)\) rounds, Heuristics for semirandom graph problems, Approximating the maximum quadratic assignment problem, Sparse universal graphs, On a generalization of Polya inequality and some of its statistical implications, Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes, Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu, Asymptotically good edge correspondence colourings, Ramsey numbers of large books, Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE, Routing with bounded buffers and hot-potato routing in vertex-symmetric networks, Near-optimal distributed edge coloring, How does the chromatic number of a random graph vary?, On sparse parity check matrices (extended abstract), Coloring k-colorable graphs in constant expected parallel time, A probabilistic algorithm for vertex cover, Probability bounds for \(n\) random events under \((n-1)\)-wise independence, Unnamed Item, Book embeddings and crossing numbers, Efficient deterministic algorithms for embedding graphs on books, Fast separator decomposition for finite element meshes, Optimal linear‐Vizing relationships for (total) domination in graphs, Random bipartite Ramsey numbers of long cycles, A Sharp Uniform Bound for the Distribution of Sums of Bernoulli Trials, A counterexample to Stein’s Equi-$n$-square Conjecture, Non-concentration of the chromatic number of a random graph, APPROXIMATE ALGORITHMS FOR GRAPH CLUSTERING PROBLEM, Paul Erdős, 1913-1996, Repetition-free longest common subsequence, Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners, Noise sensitivity of Boolean functions and applications to percolation, Colouring Steiner quadruple systems, Contributions to the problem of Zrankiewicz, Constructive lower bounds for off-diagonal Ramsey numbers, On dominated \(\ell_1\) metrics, The role assignment model nearly fits most social networks, The diameter of sparse random graphs, The giant component threshold for random regular graphs with edge faults H. Prodinger, Random regular graphs with edge faults: Expansion through cores, The communication complexity of pointer chasing, On the complexity of \(k\)-SAT, Matching colored points in the plane: Some new results, A dimension gap for continued fractions with independent digits, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, Finite Representability of Integers as $2$-Sums, When almost all sets are difference dominated in $\mathbb{Z}/n\mathbb{Z}$, A simple one dimensional glassy Kac model, Unnamed Item, Fast Nonadaptive Deterministic Algorithm for Conflict Resolution in a Dynamic Multiple-Access Channel, Unnamed Item, Unnamed Item
