BALL::TreeWidthImplementation< EditableGraph > Class Template Reference

#include <BALL/DATATYPE/GRAPH/treeWidth.h>

Classes
struct	FillInHeuristic
class	GeneralLowerBoundAlgorithm
	Generic lower bound algorithm on graphs. More...
class	GreedyX
class	MinorMinWidthCriterion
class	MinorMinWidthReducer
class	QuickBB
class	TreeDecompositionBuilder

Public Types
typedef boost::graph_traits < UndirectedGraph > ::vertex_descriptor	VertexType
typedef boost::graph_traits < UndirectedGraph > ::adjacency_iterator	NeighbourIterator
typedef boost::graph_traits < UndirectedGraph > ::vertex_iterator	VertexIterator
typedef std::pair< std::vector < Size >, Size >	EliminationOrder
typedef GeneralLowerBoundAlgorithm < MinorMinWidthCriterion, MinorMinWidthReducer >	MinorMinWidth
typedef GreedyX< FillInHeuristic >	GreedyFillIn

Detailed Description

template<class EditableGraph>
class BALL::TreeWidthImplementation< EditableGraph >

Definition at line 54 of file treeWidth.h.

Member Typedef Documentation

template<class EditableGraph >

typedef std::pair<std::vector<Size>, Size> BALL::TreeWidthImplementation< EditableGraph >::EliminationOrder

An EliminationOrder is a permutation of vertices of a graph which can be used to build a Fill-In-Graph. The TreeDecomposition of such a graph is a minimal Tree-Decomposition of the source graph, if the elimination order is perfect. first is the permutation of vertices, second is the tree width of the Three-Decomposition of such a Fill-In graph

Definition at line 191 of file treeWidth.h.

template<class EditableGraph >

typedef GreedyX<FillInHeuristic> BALL::TreeWidthImplementation< EditableGraph >::GreedyFillIn

An upperbound heuristic which computes an EliminationOrder, which can build a tree decomposition, and a treewidth of a given graph. The basic idea is to add as few as possible edges into the FillInGraph, because this should reduce the treewidth of the FillInGraph. Nevertheless, it's just a heuristic, so there is no guarantee, that the treewidth is minimal.

Exceptions

BALL::GRAPH::UnconnectedGraphException

if called on unconnected graphs

Definition at line 445 of file treeWidth.h.

template<class EditableGraph >

typedef GeneralLowerBoundAlgorithm<MinorMinWidthCriterion, MinorMinWidthReducer> BALL::TreeWidthImplementation< EditableGraph >::MinorMinWidth

Minor-Min-Width is a lowerbound algorithm for computing the treewidth. It contracts in each step a vertex u, which has minimum degree in graph, with a vertex v, which has a minimum degree in u's neighbourhood. The maximum of the minimum degrees is the lowerbound for the treewidth.

The basic idea behind this algorithm is:

• the treewidth of a graph is never lower than the treewidth of its minor
• the treewidth of a graph is never lower than the minimum degree of its vertices (because you can always find an optimal tree decomposition which contains a leaf, which has at least one vertex v, which isn't contained in the parents vertex set. For each edge of this vertex v, there must be a vertex in the leaf. So degree(v) is a minimal treewidth of this tree decomposition!)

  Exceptions

  BALL::GRAPH::UnconnectedGraphException

  if called on unconnected graphs

Definition at line 268 of file treeWidth.h.

template<class EditableGraph >

typedef boost::graph_traits<UndirectedGraph>::adjacency_iterator BALL::TreeWidthImplementation< EditableGraph >::NeighbourIterator

Definition at line 182 of file treeWidth.h.

template<class EditableGraph >

typedef boost::graph_traits<UndirectedGraph>::vertex_iterator BALL::TreeWidthImplementation< EditableGraph >::VertexIterator

Definition at line 183 of file treeWidth.h.

template<class EditableGraph >

typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor BALL::TreeWidthImplementation< EditableGraph >::VertexType

Definition at line 181 of file treeWidth.h.