Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4669273 | Bulletin des Sciences Mathématiques | 2009 | 17 Pages |
Abstract
We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n5). Finally, numerical tests reveal that it should only require O(n2) iterations in practice.
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)