Treewidth computations II. Lower bounds

被引：33

作者：

Bodlaender, Hans L. ^{[1
]}

Koster, Arie M. C. A. ^{[2
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, NL-3508 TB Utrecht, Netherlands

[2] Rhein Westfal TH Aachen, Lehrstuhl Math 2, D-52062 Aachen, Germany

来源：

INFORMATION AND COMPUTATION | 2011年 / 209卷 / 07期

关键词：

Treewidth; Lower bounds; Heuristics; Graph algorithms; ALGORITHMS; GRAPHS;

D O I：

10.1016/j.ic.2011.04.003

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

For several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs. (C) 2011 Elsevier Inc. All rights reserved.

引用

页码：1103 / 1119

页数：17

共 48 条

[1]

Ahuja R., 1993, NETWORK FLOWS THEORY

[2]

[Anonymous], 2018, Graph theory

[3]

[Anonymous], 2001, Introduction to Graph Theory

[4]

[Anonymous], 2001, The Boost Graph Library: User Guide and Reference Manual, Portable Documents

[5]

[Anonymous], 2003, COMBINATORIAL OPTIMI

[6] CHARACTERIZATION AND RECOGNITION OF PARTIAL 3-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :305-314

[7]

ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985

[8] Two short proofs concerning tree-decompositions [J].

Bellenbaum, P ;

Diestel, R .

COMBINATORICS PROBABILITY & COMPUTING, 2002, 11 (06) :541-547

[9] Treewidth lower bounds with brambles [J].

Bodlaender, Hans L. ;

Grigoriev, Alexander ;

Koster, Arie M. C. A. .

ALGORITHMICA, 2008, 51 (01) :81-98

[10] On the maximum cardinality search lower bound for treewidth [J].

Bodlaender, Hans L. ;

Koster, Arie M. C. A. .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (11) :1348-1372

← 1 2 3 4 5 →