Complexity of Finding and Enumerating Interconnection Trees

Noé Demange, Yann Strozecki

We study the problem of connecting the parts of a multipartite graph using a minimum number of edges under a matching constraint. We introduce interconnection trees, defined as mat…