Fast probabilistic algorithms for Hamiltonian circuits and matchings

From MaRDI portal

Publication:1141153

Jump to:navigation, search

DOI10.1016/0022-0000(79)90045-XzbMath0437.05040WikidataQ105583530 ScholiaQ105583530MaRDI QIDQ1141153

Dana Angluin, Leslie G. Valiant

Publication date: 1979

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian circuit random graph perfect matching probabilistic behaviour

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

Randomized algorithms in combinatorial optimization: A survey, Invariance properties of RAMs and linear time, Efficient distribution-free learning of probabilistic concepts, Nonuniform learnability, Finding Hamilton cycles in sparse random graphs, Drawing graphs in two layers, The knowledge complexity of quadratic residuosity languages, Expected time analysis for Delaunay point location, On the learnability of monotone \(k\mu\)-DNF formulae under product distributions, An improved upper bound on the non-3-colourability threshold, Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study, Average polynomial time complexity of some NP-complete problems, Weighted fractional and integral \(k\)-matching in hypergraphs, A real-time algorithm for the \((n^{2}-1)\)-puzzle, An algorithm for finding Hamilton paths and cycles in random graphs, Geometric representation of graphs in low dimension using axis parallel boxes, Asymptotic behavior of the quadratic knapsack problem, Constructing a perfect matching is in random NC, Close-to-optimal and near-optimal broadcasting in random graphs, On key storage in secure networks, On the stabbing number of a random Delaunay triangulation, The complexity of parallel search, Randomized rounding: A technique for provably good algorithms and algorithmic proofs, A parallel bucket sort, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Tight approximations for resource constrained scheduling and bin packing, Algorithms for dense graphs and networks on the random access computer, Hybridsort revisited and parallelized, Rounding algorithms for covering problems, Scalable zero knowledge via cycles of elliptic curves, Architecture independent parallel selection with applications to parallel priority queues, Finding patterns common to a set of strings, Uniform capacitated facility location problem with random input data, Communication and energy efficient routing protocols for single-hop radio networks, Exact simultaneous recovery of locations and structure from known orientations and corrupted point correspondences, On factors in random graphs, A guided tour of Chernoff bounds, On learning a union of half spaces, Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations, Context-free grammars as a tool for describing polynomial-time subclasses of hard problems, On complexity, representation and approximation of integral multicommodity flows, Efficient algorithmic learning of the structure of permutation groups by examples, Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem, Hamiltonian cycles in Cayley graphs of imprimitive complex reflection groups, Parameterized \(k\)-clustering: tractability island, An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties, Some observations on skip-lists, A special case the of dynamization problem for least cost paths, Broadcasting in complete networks with faulty nodes using unreliable calls, Equivalence of models for polynomial learnability, On-line computation of minimal and maximal length paths, Fourier 1-norm and quantum speed-up, Expected parallel time and sequential space complexity of graph and digraph problems, Approximate inference of functional dependencies from relations, Approximating minimum power edge-multi-covers, On the cell probe complexity of polynomial evaluation, Inductive reasoning and Kolmogorov complexity, Decision theoretic generalizations of the PAC model for neural net and other learning applications, On packing bipartite graphs, On the occurence of null clauses in random instances of Satisfiability, Randomized range-maxima in nearly-constant parallel time, Critical branching random walks with small drift, Graph theory (algorithmic, algebraic, and metric problems), Robust modifications of U-statistics and applications to covariance estimation problems, Using matrices to link conflict evolution and resolution in a graph model, A matrix-based approach to searching colored paths in a weighted colored multidigraph, A note on Rabin's nearest-neighbor algorithm, A fast randomized algorithm for partitioning a graph into paths of fixed length, Computing absolutely normal numbers in nearly linear time, Parallel iterated bucket sort, A graph-theoretic generalization of the Sauer-Shelah lemma, On patching algorithms for random asymmetric travelling salesman problems, Sorting, linear time and the satisfiability problem, Specification and simulation of statistical query algorithms for efficiency and noise tolerance, Learning with restricted focus of attention, Adaptive game playing using multiplicative weights, Randomized selection in \(n+C+o(n)\) comparisons, A general lower bound on the number of examples needed for learning, A simple linear expected time algorithm for finding a Hamilton path, Parallel graph algorithms that are efficients on average, Average-case analysis of the modified harmonic algorithm, Expected worst-case partial match in random quadtries, Proper learning of \(k\)-term DNF formulas from satisfying assignments, On a simple randomized algorithm for finding a 2-factor in sparse graphs, Randomised algorithms, On the chromatic forcing number of a random graph, A threshold for perfect matchings in random d-pure hypergraphs, The largest tree in a random graph, Almost all regular graphs are Hamiltonian, Limit distribution for the existence of Hamiltonian cycles in a random graph, How many random edges make a graph Hamiltonian?, Combining fuzzy information from multiple systems, Improved lower bounds for learning from noisy examples: An information-theoretic approach, Partitioning heuristics for two geometric maximization problems, A successful algorithm for the undirected Hamiltonian path problem, On some conditioning results in the probabilistic analysis of algorithms, On parallel integer sorting, Learnability with respect to fixed distributions, The greedy and Delaunay triangulations are not bad in the average case, The cardinality constrained covering traveling salesman problem, Direct bulk-synchronous parallel algorithms, An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three, Fast diagnosis of multiprocessor systems with random faults, Threshold Functions for H-factors, On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three, Unnamed Item, A randomized sorting algorithm on the BSP model, Subsums of the Harmonic Series, Branch-and-bound and backtrack search on mesh-connected arrays of processors, In-place linear probing sort, Maker Breaker on digraphs, Greedy triangulation can be efficiently implemented in the average case, Near-optimal dominating sets in dense random graphs in polynomial expected time, An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution, An analysis of heuristics for graph planarization, EFFICIENT ALGORITHMS FOR SELECTION AND SORTING OF LARGE DISTRIBUTED FILES ON DE BRUIJN AND HYPERCUBE STRUCTURES, Sparse networks supporting efficient reliable broadcasting, Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing, BOUNDS ON THE CONVERGENCE TIME OF DISTRIBUTED SELFISH BIN PACKING, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, The Hamilton circuit problem on grids, Analysis of randomized protocols for conflict-free distributed access, Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time, Finding tight Hamilton cycles in random hypergraphs faster, A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses, Memorization and Association on a Realistic Neural Model, Limit distribution for the existence of Hamiltonian cycles in a random graph. (Reprint), Reliable Broadcasting in Hypercubes with Random Link and Node Failures, Cycles and paths in edge‐colored graphs with given degrees, Unnamed Item, A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time, An approximation algorithm for the partial vertex cover problem in hypergraphs, Computational sample complexity and attribute-efficient learning, On tree width, bramble size, and expansion, An Average Case NP-complete Graph Colouring Problem, Valid Generalisation from Approximate Interpolation, The Random Bit Complexity of Mobile Robots Scattering, From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial), Random Graphs In A Neural Computation Model, Broadcasting in random graphs, Two-way chaining for non-uniform distributions, Tight Hamilton cycles in random hypergraphs, The resolution complexity of random graph \(k\)-colorability, The capacitated facility location problem with random input data, On-the-Fly Array Initialization in Less Space, Sequential Sampling for Optimal Weighted Least Squares Approximations in Hierarchical Spaces

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1141153&oldid=13194525"