wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

exact_matching (301B)

      1 # Exact matching
      2 
      3 - Input: [bipartite_graph] G with bicolored edges, integer k
      4 - Output: does G contain a [perfect_matching] with exactly k red edges
      5 
      6 [maalouly2022exact]: this is in [RP] and not known to be in [ptime]
      7 
      8 Variants:
      9 - [exact_matching_parity]
     10 - [red_blue_yellow_matching]
     11 
     12 Up: [matching]