An algorithm for finding Hamilton paths and cycles in random graphs
From MaRDI portal
Publication:1099190
DOI10.1007/BF02579321zbMath0638.05036OpenAlexW2030689634WikidataQ57401622 ScholiaQ57401622MaRDI QIDQ1099190
Béla Bollobás, Alan M. Frieze, Trevor I. Fenner
Publication date: 1987
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579321
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Related Items
Many hard examples in exact phase transitions, An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three, On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three, Hitting time for \(k\) edge-disjoint spanning trees in a random graph, Hamilton cycles in highly connected and expanding graphs, Unnamed Item, Finding a Hamilton cycle fast on average using rotations and extensions, Geodesic cycles in random graphs, An asymptotically optimal algorithm for the m-Peripatetic Salesman Problem on random inputs with discrete distribution, Quantized consensus in Hamiltonian graphs, HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle, Potential distribution on random electrical networks, Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One, On covering expander graphs by hamilton cycles, Finding tight Hamilton cycles in random hypergraphs faster, Hamiltonicity thresholds in Achlioptas processes, Local resilience of graphs, A distributed algorithm for finding Hamiltonian cycles in random graphs in \(O(\log n)\) time, A simple linear expected time algorithm for finding a Hamilton path, Longest cycles in sparse random digraphs, Tight Hamilton cycles in random hypergraphs, Hamiltonian cycle curves in the space of discounted occupational measures, Heuristic approaches for the Minimum Labelling Hamiltonian Cycle Problem, Typical values of extremal-weight combinatorial structures with independent symmetric weights
Cites Work
- Unnamed Item
- Limit distribution for the existence of Hamiltonian cycles in a random graph
- How many random edges make a graph Hamiltonian?
- Limit distribution for the existence of Hamiltonian cycles in random bipartite graphs
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- A simple linear expected time algorithm for finding a Hamilton path
- On the existence of Hamiltonian cycles in a class of random graphs
- On the strength of connectedness of a random graph
- A Dynamic Programming Approach to Sequencing Problems
