The Unimodular Intersection Problem

Shmuel Onn
Technion - Israel Institute of Technology

PDF

Minisymposium: GENERAL SESSION TALKS

Content: We show that finding minimally intersecting n paths from s to t in a directed graph or n perfect matchings in a bipartite graph can be done in polynomial time. This holds more generally for unimodular set systems.

Back to all abstracts