Branch decomposition heuristics for linear matroids

作者：Ma Jing; Margulies Susan; Hicks Illya V^*; Goins Edray

来源：Discrete Optimization, 2013, 10(2): 102-119.

DOI：10.1016/j.disopt.2012.11.004

• Linear matroid
• Branchwidth
• Branch decomposition
• Classification
• Max-flow
• Matroid intersection

This paper presents three new heuristics which utilize classification, max-flow, and matroid intersection algorithms respectively to derive near-optimal branch decompositions for linear matroids. In the literature, there are already excellent heuristics for graphs, however, no practical branch decomposition methods for general linear matroids have been addressed yet. Introducing a %26quot;measure%26quot; which compares the %26quot;similarity%26quot; of elements of a linear matroid, this work reforms the linear matroid into a similarity graph. Then, the classification method, the max-flow method, and the mat-flow method, all based on the similarity graph, are utilized on the similarity graph to derive separations for a near-optimal branch decomposition. Computational results using the methods on linear matroid instances are shown respectively.

• 出版日期2013-5