Branch decompositions and minor containment
Illya V. Hicks · Networks · 2003
Abstract Given a simple graph G , a simple connected graph H , and a branch decomposition of G of width k , we present a practical algorithm to test if H is a minor of G . The notion of branch decompositions and its related connectivity invariant for graphs, branchwidth, were introduced by Robertson and Seymour. The algorithm that we present follows the general framework for such an algorithm sketched by Robertson and Seymour with the addition of pruning techniques for runtime speedup. © 2003 Wiley Periodicals, Inc.