首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Solving the linear matroid parity problem as a sequence of matroid intersection problems
Authors:James B Orlin  John H Vande Vate
Institution:(1) Sloan School of Management, Massachusetts Institute of Technology, 02139 Cambridge, MA, USA;(2) Industrial and Systems Engineering, Georgia Institute of Technology, 30332 Atlanta, GA, USA
Abstract:In this paper, we present an O(r 4 n) algorithm for the linear matroid parity problem. Our solution technique is to introduce a modest generalization, the non-simple parity problem, and identify an important subclass of non-simple parity problems called lsquoeasyrsquo parity problems which can be solved as matroid intersection problems. We then show how to solve any linear matroid parity problem parametrically as a sequence of lsquoeasyrsquo parity problems.In contrast to other algorithmic work on this problem, we focus on general structural properties of dual solutions rather than on local primal structures. In a companion paper, we develop these ideas into a duality theory for the parity problem.
Keywords:Matroid parity  matroids  polynomial algorithms  matching  matroid intersection
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号