Planar branch decompositions I: The ratcatcher

Planar branch decompositions I: The ratcatcher

0.00 Avg rating0 Votes
Article ID: iaor2007345
Country: United States
Volume: 17
Issue: 4
Start Page Number: 402
End Page Number: 412
Publication Date: Sep 2005
Journal: INFORMS Journal On Computing
Authors:
Abstract:

The notion of branch decompositions and its related connectivity invariant for graphs, branchwidth, were introduced by Robertson and Seymour in their series of papers that proved Wagner's conjecture. Branch decompositions can be used to solve NP-hard problems modeled on graphs, but finding optimal branch decompositions of graphs is also NP-hard. This is the first of two papers dealing with the relationship of branchwidth and planar graphs. A practical implementation of an algorithm of Seymour and Thomas for only computing the branchwidth (not optimal branch decomposition) of any planar hypergraph is proposed. This implementation is used in a practical implementation of an algorithm of Seymour and Thomas for computing the optimal branch decompositions for planar hypergraphs that is presented in the second paper. Since memory requirements can become an issue with this algorithm, two other variations of the algorithm to handle larger hypergraphs are also presented.

Reviews

Required fields are marked *. Your email address will not be published.