Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-10T03:53:01.580Z Has data issue: false hasContentIssue false
  • English
  • Français

Best Odds for Finding a Perfect Matching in a Bipartite Graph

Published online by Cambridge University Press:  31 July 2006

W. PAULSEN
W. PAULSEN
Affiliation:
Department of Mathematics and Statistics, Arkansas State University, PO Box 70, State University, AR 72432, USA (e-mail: wpaulsen@math.astate.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We will study the best way to reveal a hidden perfect matching in a balanced bipartite graph by eliminating edges, one by one, in the hope that the eliminated edge is not part of the mystery perfect matching. We will look for the strategy that maximizes the odds of finding the perfect matching without revealing a fixed number of the edges in that perfect matching. For a complete bipartite graph, this is equivalent to finding a mystery permutation via negative guesses with only a fixed number of incorrect negative guesses.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 5 , September 2006 , pp. 753 - 763
Copyright
2006 Cambridge University Press