Graphs with Branchwidth at Most Three |
| |
Authors: | Hans L Bodlaender Dimitrios M Thilikos |
| |
Institution: | Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, the Netherlandsf1;Department of Computer Science DC 2117, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, N2L 32G1, Canada, f2 |
| |
Abstract: | In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition. |
| |
Keywords: | graph algorithms branchwidth obstruction set graph minors reduction rule |
本文献已被 ScienceDirect 等数据库收录! |
|