A branch-and-price-and-cut method for computing an optimal bramble
Type :
Article
Publication Status :
published
Access :
restrictedAccess
Abstract
Given an undirected graph, a bramble is a set of connected subgraphs (called bramble elements) such that every pair of subgraphs either contains a common node, or such that an edge ( i , j ) exists with node i belonging to one subgraph and node j belonging to the other. In this paper we examine the problem of finding the bramble number of a graph, along with a set of bramble elements that yields this number. The bramble number is the largest cardinality of a minimum hitting set over all bramble elements on this graph. A graph with bramble number k has a treewidth of k - 1 . We provide a branch-and-price-and-cut method that generates columns corresponding to bramble elements, and rows corresponding to hitting sets. We then examine the computational efficacy of our algorithm on a randomly generated data set.
Source :
Discrete Optimization
Date :
2015
Volume :
18
Publisher :
Elsevier
URI
http://hdl.handle.net/10679/4057http://www.sciencedirect.com/science/article/pii/S1572528615000511
Collections
Share this page