Idioma:

Graphs with Branchwidth at Most Three

Bodlaender, Hans L ; Thilikos, Dimitrios M

Journal of algorithms, 1999-08, Vol.32 (2), p.167-194 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Graphs with Branchwidth at Most Three
Autor: Bodlaender, Hans L ; Thilikos, Dimitrios M
Assuntos: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; branchwidth ; Computer science; control theory; systems ; Exact sciences and technology ; graph algorithms ; graph minors ; Information retrieval. Graph ; obstruction set ; reduction rule ; Theoretical computing
É parte de: Journal of algorithms, 1999-08, Vol.32 (2), p.167-194
Descrição: 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.
Editor: San Diego, CA: Elsevier Inc
Idioma: Inglês

Links

Voltar para lista de resultados