Format:
19 S. :
,
graph. Darst.
Series Statement:
ZIB-Report 2004,43
Content:
Abstract: "The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in [3]. In experiments it was shown that this lower bound improves upon other treewidth lower bounds [3]. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, blocks of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described."
Language:
English
Subjects:
Computer Science
Keywords:
Forschungsbericht
Bookmarklink