Premium
Branch decompositions and minor containment
Author(s) -
Hicks Illya V.
Publication year - 2004
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.10099
Subject(s) - minor (academic) , pruning , speedup , computer science , breadth first search , graph , simple (philosophy) , algorithm , combinatorics , mathematics , theoretical computer science , parallel computing , agronomy , philosophy , epistemology , political science , law , biology
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.