Samer Nofal

Maximum Induced Matching: Recursive Computation and an Availability-Uniform Branch-Length Analysis

Induced matchings are a fundamental graph-theoretic concept with applications in secure communication, network flow, and very-large-scale integration. An induced matching in a graph is a set of pairwise non-adjacent edges such that no edge of the graph joins the endpoints of two distinct edges in the set. A maximum ind...