Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 9 von 10
Zurück zur Trefferliste

Treewidth Lower Bounds with Brambles

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-8878
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Hans L. Bodlaender, Alexander Grigoriev, Arie M.C.A. Koster
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:brambles; branchwidth; lower bounds; treewidth
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
Datum der Erstveröffentlichung:13.12.2005
Schriftenreihe (Bandnummer):ZIB-Report (05-54)
ZIB-Reportnummer:05-54
Verlagspublikation:Appeared in: Algorithmica 51 (2008) 81-98. An extended abstract appeared in: Proc. 13th Ann. Europ. Symp. on Algorithms, ESA 2005, LNCS 3669, Springer 2005, pp. 391-402
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.