Planar branch decompositions II: The cycle method

Planar branch decompositions II: The cycle method

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

This is the second of two papers dealing with the relationship of branchwidth and planar graphs. Branchwidth and branch decompositions, introduced by Robertson and Seymour, have been shown to be beneficial for both proving theoretical results on graphs and solving NP-hard problems modeled on graphs. The first practical implementation of an algorithm of Seymour and Thomas for computing optimal branch decompositions of planar hypergraphs is presented. This algorithm encompasses another algorithm of Seymour and Thomas for computing the branchwidth of any planar hypergraph, whose implementation is discussed in the first paper. The implementation also includes the addition of a heuristic to decrease the run times of the algorithm. This method, called the cycle method, is an improvement on the algorithm by using a ‘divide-and-conquer’ approach.

Reviews

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