ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Treewidth Lower Bounds with Brambles (2005)

Bodlaender, Hans L. ; Grigoriev, Alexander ; Koster, Arie M.C.A.

add to mindlist on the mindlist

Details

Publication Date: 2014-11-10

Description: In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs.

Keywords: ddc:000

Language: English

Type: reportzib , doc-type:preprint

Format: application/pdf

Format: application/postscript

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview

hit 1 - 1 | 1 hit