The cook-book approach to the differential equation method

DOI10.1016/j.cosrev.2010.04.002zbMath1302.05168OpenAlexW2011146667WikidataQ115358379 ScholiaQ115358379MaRDI QIDQ465658

Dieter Mitsche, Josep Diaz

Publication date: 24 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cosrev.2010.04.002

zbMATH Keywords

random regular graphsdifferential equation methodballs and binsrandom Boolean formulae

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Enumeration in graph theory (05C30) Paths and cycles (05C38) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Asymptotic bounds on total domination in regular graphs, A gentle introduction to the differential equation method and dynamic concentration, The matching process and independent process in random regular graphs and hypergraphs

Cites Work

• A threshold for unsatisfiability
• Encores on cores
• The first cycles in an evolving graph
• A guided tour of Chernoff bounds
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Large independent sets in random regular graphs
• The isoperimetric number of random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• NP-completeness of some generalizations of the maximum matching problem
• Size and connectivity of the \(k\)-core of a random graph
• On the independence and chromatic numbers of random regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• Randomization and approximation techniques in computer science. 2nd international workshop, RANDOM '98. Barcelona, Spain, October 8--10, 1998. Proceedings
• Small maximal matchings in random graphs.
• Analysis of greedy algorithms on graphs with bounded degrees
• Bounds on the max and min bisection of random cubic and random 4-regular graphs
• Differential equations for random processes and random graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• On the satisfiability threshold of formulas with three literals per clause
• Bounds on the bisection width for random \(d\)-regular graphs
• Weighted sums of certain dependent random variables
• Acyclic edge colorings of graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• A simple solution to the k‐core problem
• Uniform generation of random regular graphs of moderate degree
• On the chromatic number of a random 5-regular graph
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• New methods to color the vertices of a graph
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the independence number of random cubic graphs
• The acyclic edge chromatic number of a random d‐regular graph is d + 1
• Generating Random Regular Graphs Quickly
• Minimum independent dominating sets of random cubic graphs
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Random Formulas Have Frozen Variables
• On the Independent Domination Number of Random Regular Graphs
• Colouring Random 4-Regular Graphs
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Probability Inequalities for Sums of Bounded Random Variables
• Advanced Lectures on Machine Learning
• Thek-Core and Branching Processes
• Probability and Computing
• The probabilistic analysis of a greedy satisfiability algorithm
• Solutions of ordinary differential equations as limits of pure jump markov processes
• On the existence of a factor of degree one of a connected random graph
• Concentration of Measure for the Analysis of Randomized Algorithms
• Almost all graphs with average degree 4 are 3-colorable
• Large deviations
• Random 2-SAT: Results and problems
• Lower bounds for random 3-SAT via differential equations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item