OAI/Computability/LoopMatching/CountDecomposition.lean

GitHub source file

6 declarations, 0 contain sorry, 0 declared as axioms

Polynomial-time approximation of weighted matchings with singleton loops.

  1. theorem OAI.LoopMatching.loopVertices_card_le line 11
  2. theorem OAI.LoopMatching.countWithLoops_eq_zero_of_lt line 16
  3. theorem OAI.LoopMatching.count_eq_sum_countWithLoops line 29
  4. theorem OAI.LoopMatching.weight_eq_zero_of_loopMultiplicity_eq_zero line 47
  5. theorem OAI.LoopMatching.weight_eq_zero_of_multiplicity_eq_zero line 55
  6. theorem OAI.LoopMatching.count_eq_zero_of_forall_weight_eq_zero line 63