Premium
Tangle bases: Revisited
Author(s) -
Hicks Illya V.,
Brimkov Boris
Publication year - 2021
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21979
Subject(s) - tangle , submodular set function , mathematics , basis (linear algebra) , matroid , combinatorics , constructive , graph , discrete mathematics , pure mathematics , computer science , geometry , process (computing) , operating system
The concept of branch decomposition was first introduced by Robertson and Seymour in their proof of the Graph Minors Theorem, and can be seen as a measure of the global connectivity of a graph. Since then, branch decomposition and branchwidth have been used for computationally solving combinatorial optimization problems modeled on graphs and matroids. General branchwidth is the extension of branchwidth to any symmetric submodular function defined over a finite set. General branchwidth encompasses graphic branchwidth, matroidal branchwidth, and rankwidth. A tangle basis is related to a tangle, a notion also introduced by Robertson and Seymour; however, a tangle basis is more constructive in nature. It was shown in [I. V. Hicks. Graphs, branchwidth, and tangles! Oh my! Networks , 45:55‐60, 2005] that a tangle basis of order k is coextensive to a tangle of order k . In this paper, we revisit the construction of tangle bases computationally for other branchwidth parameters and show that the tangle basis approach is still competitive for computing optimal branch decompositions for general branchwidth.