Partition functions for dense instances of combinatorial enumeration problems
From MaRDI portal
Abstract: Given a complete graph with positive weights on its edges, we define the weight of a subset of edges as the product of weights of the edges in the subset and consider sums (partition functions) of weights over subsets of various kinds: cycle covers, closed walks, spanning trees. We show that if the weights of the edges of the graph are within a constant factor, fixed in advance, of each other then the bulk of the partition function is concentrated on the subsets of a particularly simple structure: cycle covers with few cycles, walks that visit every vertex only few times, and spanning trees with small degree of every vertex. This allows us to construct a polynomial time algorithm to separate graphs with many Hamiltonian cycles from graphs that are sufficiently far from Hamiltonian.
This page was built for publication: Partition functions for dense instances of combinatorial enumeration problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6241839)
