2009, English, Article edition: Constructing brambles Chapelle, Mathieu; Mazoit, Frédéric; Todinca, Ioan

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/205163
Physical Description
  • text
Published
  • HAL - CCSD
  • 2009
Language
  • English

Edition details

Title
  • Constructing brambles
Author
  • Chapelle, Mathieu
  • Mazoit, Frédéric
  • Todinca, Ioan
Published
  • HAL - CCSD
  • 2009
Physical Description
  • text
Subjects
Notes
  • Given an arbitrary graph G and a number k, it is well-known by a result of Seymour and Thomas that G has treewidth strictly larger than k if and only if it has a bramble of order k + 2. Brambles are used in combinatorics as certificates proving that the treewidth of a graph is large. From an algorithmic point of view there are several algorithms computing tree-decompositions of G of width at most k, if such decompositions exist and the running time is polynomial for constant k. Nevertheless, when the treewidth of the input graph is larger than k, to our knowledge there is no algorithm constructing a bramble of order k + 2. We give here such an algorithm, running in O(n^{k+4} ) time. Moreover, for classes of graphs with polynomial number of minimal separators, we define a notion of compact brambles and show how to compute compact brambles of order k + 2 in polynomial time, not depending on k.
  • HAL:hal-00407682, version 1
  • HAL:http:/​/​hal.archives-ouvertes.fr/​hal-00407682/​en/​
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment