12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Odd minimum cut-sets and b-matchings revisited
View graph of relations

« Back

Odd minimum cut-sets and b-matchings revisited

Research output: Contribution to journalJournal article

Published

Journal publication date2008
JournalSIAM Journal on Discrete Mathematics
Journal number4
Volume22
Number of pages8
Pages1480-1487
Original languageEnglish

Abstract

The famous Padberg–Rao separation algorithm for b-matching polyhedra can be implemented to run in O(|V|^2|E| log(|V|^2/|E|)) time in the uncapacitated case, and in O(|V||E|^2 log(|V|^2/|E|)) time in the capacitated case. We give a new and simple algorithm for the capacitated case which can be implemented to run in O(|V|^2|E|\log(|V|^2/|E|)) time.