5 votes

Algorithms to count perfect matchings in near planar graphs

Graphs of bounded genus (both orientable or non-orientable): G. Tesler, Matchings in Graphs on Non-orientable Surfaces, Journal of Combinatorial Theory, Series B, Volume 78, Issue 2 (2000), 198-231. ...
Jan Kyncl's user avatar
  • 5,981
1 vote

Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

For random graphs, there are algorithms that are efficient on average. See for example A fast algorithm on average for solving the Hamilton Cycle problem by Michael Anastos and the references therein. ...
Timothy Chow's user avatar
  • 78.1k

Only top scored, non community-wiki answers of a minimum length are eligible