On some algorithmic aspects of hypergraphic matroids |
| |
Affiliation: | 1. CNRS and Université Clermont Auvergne, Clermont-Ferrand, France;2. IBM T J Watson Research Center, P. O. Box 218, Yorktown Heights, NY 10598, USA |
| |
Abstract: | Hypergraphic matroids were studied first by Lorea [23] and later by Frank et al. [11]. They can be seen as generalizations of graphic matroids. Here we show that several algorithms developed for the graphic case can be extended to hypergraphic matroids. We treat the following: the separation problem for the associated polytope, testing independence, separation of partition inequalities, computing the rank of a set, computing the strength, computing the arboricity and network reinforcement. |
| |
Keywords: | Hypergraphic matroids Combinatorial optimization Network reinforcement |
本文献已被 ScienceDirect 等数据库收录! |
|