Fast probabilistic algorithms for Hamiltonian circuits and matchings

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 circuitrandom graphperfect matchingprobabilistic 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 (only showing first 100 items - show all)

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 ⋮ Vertex-connectivity for node failure identification in Boolean network tomography ⋮ 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 ⋮ The square of a Hamilton cycle in randomly perturbed graphs ⋮ An approximation algorithm for the partial vertex cover problem in hypergraphs ⋮ Limitations of the QRQW and EREW PRAM models ⋮ Computational sample complexity and attribute-efficient learning ⋮ Sequential schemes for frequentist estimation of properties in statistical model checking ⋮ 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 ⋮ 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

Cites Work

• Hamiltonian circuits in random graphs
• Time bounded random access machines
• Graphs on unlabelled nodes with a given number of edges
• For How Many Edges is a Digraph Almost Certainly Hamiltonian?
• On colouring random graphs
• A Fast Monte-Carlo Test for Primality
• Paths, Trees, and Flowers
• Probabilistic automata
• On the existence of a factor of degree one of a connected random graph
• The complexity of theorem-proving procedures
• Some Theorems on Abstract Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast probabilistic algorithms for Hamiltonian circuits and matchings