Approximately Counting Hamilton Paths and Cycles in Dense Graphs

DOI10.1137/S009753979426112XzbMath0907.68111OpenAlexW2021084480WikidataQ57401548 ScholiaQ57401548MaRDI QIDQ4210094

Martin Dyer, Alan M. Frieze, Mark R. Jerrum

Publication date: 20 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979426112x

zbMATH Keywords

Hamilton cyclesdensefpras

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

On the number of circuits in random graphs, How many needles are in a haystack, or how to solve \#P-complete counting problems fast, Complexity and approximability of the cover polynomial, Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs, A faster FPTAS for counting two-rowed contingency tables, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Set graphs. II. Complexity of set graph recognition and similar problems, Approximately Counting Embeddings into Random Graphs